Exam-style question
Try this first
A recursive algorithm makes two recursive calls for every input element and continues until all elements have been processed. Which complexity is the most appropriate general classification?.
- A.O(1)
- B.O(log n)
- C.O(n)
- D.O(2^n)
Model answer
What a good answer should say
- O(2^n)
Explanation
Why this works
When the number of calls branches into two calls at each level, the number of calls can grow exponentially with n. This is represented by O(2^n).
Common mistake
No common mistake is linked to this question yet.