The given diagram shows the flowchart for a recursive function \(A(n)\).…
2016
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 value (accurate up to two decimal positions) of \(α\) is ____________ .
Attempted by 44 students.
Show answer & explanation
Correct answer: 2.32
Key idea: count the maximum number of recursive calls of size n/2 made by a single call to A(n), then use the recurrence T(n) = k T(n/2) + O(1) so that the exponent is α = log2(k).
From A(n), the function immediately makes one call A(n/2). (Call 1)
At the first decision, to get the worst case we follow the branch that continues calling more: this leads to another A(n/2). (Call 2) Then that path calls yet another A(n/2). (Call 3)
Continuing to choose branches that maximize calls leads down to a further A(n/2). (Call 4) and finally one more A(n/2). (Call 5)
Thus in the worst case a single call to A(n) spawns 5 recursive calls of size n/2, so the recurrence is T(n) = 5 T(n/2) + O(1).
Therefore α = log2(5). Compute log2(5) ≈ 2.321928…, which rounded to two decimal places is 2.32.
Answer: 2.32