What is the time complexity for the following C module? Assume that n>0 . int…
2014
What is the time complexity for the following C module? Assume that n>0 . int module(int n) { if (n == 1) return 1; else return (n + module(n-1)); }
- A.
O(n)
- B.
O(log n)
- C.
O(n2)
- D.
O(n!)
Attempted by 104 students.
Show answer & explanation
Correct answer: A
The function is recursive and calls itself with n-1 until n equals 1.
This results in n recursive calls, performing constant work at each step.
The recurrence relation T(n) = T(n-1) + O(1) resolves to a total time complexity of O(n).