The given diagram shows the flowchart for a recursive function A(n). Assume…
2024
The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst-case time complexity of this function is O(nα), then the least possible (accurate up to two decimal position) of α is _______.
- A.
2.2
- B.
2.9
- C.
8.9
- D.
7.8
Attempted by 31 students.
Show answer & explanation
Correct answer: A
To find the worst-case time complexity of the function.
Worst case happens in case of recursive. So, find out the recursive calls on the longer route.
There are 5 such recursive calls to A (n/2).
So, recurrence relation will become like:
A (n) = 5A (n/2) + O(1)
where O(1) is constant
By using master’s theorem,
a = 5, b =2
