GATE CS 2016 Set 2 Q.49 (CS Q.39): Asymptotic Analysis and Time/Space Complexity

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^\alpha)$ , then the least possible value (accurate up to two decimal positions) of $\alpha$ is ________.

Flowchart for recursive function A(n). Starting at Start, control passes through an A(n/2) call to Decision Diamond 1. From Diamond 1, the left branch calls A(n/2) and returns (2 calls). The right branch passes through two sequential A(n/2) calls to Decision Diamond 2. From Diamond 2, the right branch returns (3 calls total), while the down branch calls A(n/2) to reach Decision Diamond 3. From Diamond 3, the right branch returns (4 calls total), while the left branch calls A(n/2) and returns (5 calls total). Worst-case execution path makes 5 recursive calls of size n/2. — Flowchart for Recursive Function A(n)

Your answer

Official answer and solution

Accepted answers: 2.2 to 2.4
From: Official GATE 2016 answer key

Solution

Trace all execution paths in the flowchart to find the worst-case number of recursive calls, then apply the Master Theorem.

Trace all possible paths from Start to Return in the flowchart:

Path 1: Start $\to A(n/2) \to$ Diamond 1 Left $\to A(n/2) \to$ Return.
Total recursive calls: $1 + 1 = 2$ calls.

Path 2: Start $\to A(n/2) \to$ Diamond 1 Right $\to A(n/2) \to A(n/2) \to$ Diamond 2 Right $\to$ Return.
Total recursive calls: $1 + 1 + 1 = 3$ calls.

Path 3: Start $\to A(n/2) \to$ Diamond 1 Right $\to A(n/2) \to A(n/2) \to$ Diamond 2 Down $\to A(n/2) \to$ Diamond 3 Right $\to$ Return.
Total recursive calls: $1 + 1 + 1 + 1 = 4$ calls.

Path 4: Start $\to A(n/2) \to$ Diamond 1 Right $\to A(n/2) \to A(n/2) \to$ Diamond 2 Down $\to A(n/2) \to$ Diamond 3 Left $\to A(n/2) \to$ Return.
Total recursive calls: $1 + 1 + 1 + 1 + 1 = 5$ calls.

In the worst case, the function executes Path 4, making 5 recursive calls of input size $n/2$ . All other statements take $O(1)$ time, yielding the recurrence:

T(n) = 5 T(n/2) + \Theta(1)

By the Master Theorem (Case 1) with $a = 5, b = 2, f(n) = \Theta(1)$ :

n^{\log_b a} = n^{\log_2 5}

\alpha = \log_2 5 = \frac{\ln 5}{\ln 2} \approx \frac{1.609438}{0.693147} \approx 2.3219

Rounding to two decimal positions gives $\alpha = 2.32$ .

Final answer

2.32

Common trap

Missing the initial $A(n/2)$ before Diamond 1 or miscounting the sequential calls along the right branch of Diamond 1.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 49 of 65, printed as CS Q.39
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source