GATE CS 2013 Q.31 (CS Q.31): Data Types, Operators and Control Flow

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

$\Theta(n^2)$

$\Theta(n^2 \log n)$

$\Theta(n^3)$

$\Theta(n^3 \log n)$

Official answer and solution

Solution

Count the number of iterations of the nested loops and sum the incremental updates to variable k.

Let us analyze the loops in unknown(int n):

Outer loop: for (i = n/2; i <= n; i++)
The index $i$ ranges from $n/2$ to $n$ . The number of iterations is:
$(n - n/2 + 1) = \Theta(n)$
Inner loop: for (j = 2; j <= n; j = j * 2)
The index $j$ takes values $2, 4, 8, 16, \dots, 2^{\lfloor \log_2 n \rfloor}$ .
The number of iterations is $\lfloor \log_2 n \rfloor = \Theta(\log n)$ .
Loop body: k = k + n/2;
This statement executes for each combination of the outer and inner loop iterations:
$\text{Total executions} = \Theta(n) \times \Theta(\log n) = \Theta(n \log n)$
In each execution, the value added to $k$ is $n/2 = \Theta(n)$ . Since $k$ starts at 0, the final value returned is:
$k = \sum_{\text{iterations}} \dfrac{n}{2} = \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)$ .

Final answer

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

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