GATE CS 2016 Set 2 Q39 — Asymptotic Worst Case Time and Space Complexity

In the worst-case scenario, the recursive function $A(n)$ follows the path in the flowchart that maximizes the number of recursive calls.

From the flowchart, when $n$ is odd, the function branches to make $5$ recursive calls of size approximately $n/2$ (specifically, $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$). When $n$ is even, it makes fewer recursive calls. Therefore, the worst-case recurrence relation is:

Applying the Master Theorem for recurrences of the form $T(n) = aT(n/b) + \Theta(n^k)$:

• $a = 5$
• $b = 2$
• $k = 0$

Since $\log_b a = \log_2 5 \approx 2.3219 > k$, the time complexity is:

Comparing this with $O(n^\alpha)$, the least possible value of $\alpha$ is $\log_2 5 \approx 2.32$.