GATE CS 2013 Q31 — Asymptotic Worst Case Time and Space Complexity

Consider the following function:

int unknown(int n){ 

int i, j, k=0; 
for (i=n/2; i<=n; i++) 
    for (j=2; j<=n; j=j*2) 
        k = k + n/2; 
 return (k); 

}

The return value of the function is

View worked solution

Answer: B

To find the return value of the function, we need to determine the final value of the variable $k$ . Let's analyze the loops step-by-step:

Outer Loop:
```
for (i = n/2; i <= n; i++)
```
The loop variable $i$ $i$ starts at $\frac{n}{2}$ $\frac{n}{2}$ and increments by $1$ $1$ until it reaches $n$ $n$ .
The number of iterations of this loop is: $\left(n - \frac{n}{2} + 1\right) = \Theta(n)$
Inner Loop:
```
for (j = 2; j <= n; j = j*2)
```
The loop variable $j$ $j$ starts at $2$ $2$ and doubles in each iteration ( $2, 4, 8, 16, \dots$ $2, 4, 8, 16, \dots$ ).
The number of iterations of this loop is: $\Theta(\log n)$

Total Executions of the Inner Statement:

Since the loops are nested and independent of each other's loop variables, the statement inside the inner loop is executed:

\text{Total Executions} = \Theta(n) \times \Theta(\log n) = \Theta(n \log n)

Calculating the Return Value $k$ :

In each execution of the inner statement, the value added to $k$ is $\frac{n}{2}$ , which is $\Theta(n)$ .

Therefore, the final value of $k$ returned by the function is:

k = \sum_{\text{outer}} \sum_{\text{inner}} \frac{n}{2}

k = \Theta(n \log n) \times \Theta(n) = \Theta(n^2 \log n)

Thus, the return value of the function is $\Theta(n^2 \log n)$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions