PA of Algorithms Q74

74The given diagram shows the flow chart 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 value (accurate up to two decimal positions) of a is ________.
Flow chart for Recursive Function A(n)

Note: Numerical type question

Option : A
Explanation :
The worst case recurrence reaction for flow chart is
T(n) = 5 T(n/2)+ 1
Apply master’s method
n ^log₂⁵ ⇒ n^2.32 > 1
T(n) = O(n^2.32)
So, α = 2.32

Forgot your password?

I agree with the Terms.