Project ForgeThe 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. The flowchart begins with one A(n/2) call, then reaches a decision diamond with two branches: one branch makes one more A(n/2) call and returns; the other branch makes two more A(n/2) calls before reaching a second decision diamond, which either returns directly, or makes one more A(n/2) call before reaching a third decision diamond whose two branches each return (one after one further A(n/2) call, one directly). If the worst case time complexity of this function is O(n^α), then the least possible value (accurate up to two decimal positions) of α is ____.
Explanation
Since each diamond is a decision (only ONE branch is taken per execution, not both), the worst-case path is whichever single path through the flowchart invokes the most A(n/2) calls. Tracing all paths: (initial call) + (branch to 2nd diamond via 2 more calls) + (branch down through the 3rd diamond via 1 more call) + (branch through 1 final call before returning) = 1+2+1+1 = 5 total recursive calls along the longest path. So the worst-case recurrence is T(n) = 5T(n/2) + O(1). By the Master theorem, T(n) = Θ(n^(log₂5)), and log₂5 ≈ 2.3219, which rounds to 2.32.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.