Exam-style question
Try this first
Consider this Python 3 code: for i in range(n): for j in range(n): print(i, j) What is the time complexity?.
- A.O(1)
- B.O(log n)
- C.O(n)
- D.O(n^2)
Model answer
What a good answer should say
- O(n^2)
Explanation
Why this works
The outer loop runs n times and, for each of those iterations, the inner loop also runs n times. This gives n multiplied by n operations, or O(n^2), which is polynomial time.
Common mistake
No common mistake is linked to this question yet.