GateAI
Asymptotic Analysis

GATE CSE 2016 Set 2 · Q39

NAT2 marksMedium

Time

The given diagram shows the flowchart for a recursive function A(n)\text{A}(n). Assume that all statements, except for the recursive calls, have O(1)O(1) time complexity. If the worst case time complexity of this function is O(nα)O(n^\alpha), then the least possible value (accurate up to two decimal positions) of α\alpha is _______.

GATE CSE 2016 Set 2 Q39 diagram

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 2.32 (±0.12) (±0.12)

Asymptotic Analysis

To determine the worst-case time complexity, we trace all execution paths through the flowchart to find the path that executes the maximum number of recursive calls of size n/2n/2:

  1. From Start, there is 11 recursive call A(n/2)\text{A}(n/2).

  2. At the first decision diamond:

    • Left branch: 11 recursive call A(n/2)\text{A}(n/2) and returns   ⟹  1+1=2\implies 1 + 1 = 2 calls total.

    • Right branch: 22 recursive calls A(n/2)\text{A}(n/2), bringing the total so far to 1+2=31 + 2 = 3 calls, followed by the second decision diamond.

  3. At the second decision diamond:

    • Right branch: Returns immediately   ⟹  3\implies 3 calls total.

    • Down branch: 11 recursive call A(n/2)\text{A}(n/2), followed by the third decision diamond   ⟹  3+1=4\implies 3 + 1 = 4 calls so far.

  4. At the third decision diamond:

    • Left branch: 11 recursive call A(n/2)\text{A}(n/2) and returns   ⟹  4+1=5\implies 4 + 1 = 5 calls total.

    • Right branch: Returns immediately   ⟹  4\implies 4 calls total.

The worst-case path executes a total of 55 recursive calls of size n/2n/2. Thus, the recurrence relation for the worst-case time complexity is:

T(n)=5T(n2)+O(1)T(n) = 5T\left(\frac{n}{2}\right) + O(1)

Using the Master Theorem for T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n) where a=5a = 5, b=2b = 2, and f(n)=O(1)f(n) = O(1):

c=log⁡ba=log⁡25≈ln⁡5ln⁡2≈1.60940.6931≈2.32c = \log_b a = \log_2 5 \approx \frac{\ln 5}{\ln 2} \approx \frac{1.6094}{0.6931} \approx 2.32

Since f(n)=O(n0)f(n) = O(n^0) and 0<log⁡250 < \log_2 5, the worst-case time complexity is Θ(nlog⁡25)=Θ(n2.32)\Theta(n^{\log_2 5}) = \Theta(n^{2.32}).

Therefore, the least possible value of α\alpha is 2.32 (accepted range: 2.2 to 2.4).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Asymptotic Analysis previous year question is Q39 of the GATE CSE 2016 Set 2 paper. Find more GATE CSE PYQs on Asymptotic Analysis in Algorithms, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Asymptotic Analysis PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Asymptotic Analysis in GATE CSE

Asymptotic Analysis has 31 GATE CSE PYQs across 19 papers from 2011 to 2026. This is the only 2-mark NAT question among them, and it is the only one in GATE CSE 2016 Set 2.

How GATE tests Asymptotic Analysis

More from GATE CSE 2016 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2016 Set 2 · Q39 · NAT

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 …

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.