Exam-style question
Try this first
Derive the time complexity of this Python 3 algorithm: for i in range(n): for j in range(i): print(i, j) Give a Big-O classification and justify your answer.
Model answer
What a good answer should say
- The time complexity is O(n^2).
- The inner loop runs 0 times when i is 0, once when i is 1, twice when i is 2, and so on, up to approximately n times.
- The total number of executions is therefore 0 + 1 + 2 + ...
- + (n - 1), which grows proportionally to n^2.
Explanation
Why this works
Although the inner loop does not run exactly n times for every outer-loop iteration, its total number of executions is a triangular sum. That sum grows quadratically, so the algorithm is classified as O(n^2), rather than O(n).
Common mistake
No common mistake is linked to this question yet.