GATE CS 2017 Set 2 Q.38 (CS Q.38): Asymptotic Analysis and Time/Space Complexity

Consider the following C function.

int fun(int n) {
    int i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j < n; j += i) {
            printf("%d %d", i, j);
        }
    }
}

Time complexity of fun in terms of $\Theta$ notation is

$\Theta(n\sqrt{n})$

$\Theta(n^2)$

$\Theta(n \log n)$

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

Official answer and solution

Official answer: C
From: Official GATE 2017 answer key

Solution

Formulate the exact double summation for the number of print statements executed and evaluate the sum using the harmonic series.

Examine the nested loops:

The outer loop runs for $i = 1, 2, \dots, n$ .
For a given $i$ , the inner loop initializes $j = 1$ , continues while $j < n$ , and increments $j$ by $i$ at each step (j += i).

The values taken by $j$ are $1, 1+i, 1+2i, \dots, 1+k i$ such that $1 + k i < n$ .
The number of iterations for a given $i$ is:

\left\lceil \frac{n - 1}{i} \right\rceil \approx \frac{n}{i}

Summing the total number of iterations over all $i$ from 1 to $n$ :

\text{Total Operations} = \sum_{i=1}^n \left\lceil \frac{n-1}{i} \right\rceil = \Theta\left( n \sum_{i=1}^n \frac{1}{i} \right)

Recall that $\sum_{i=1}^n \frac{1}{i} = H_n = \ln n + O(1) = \Theta(\log n)$ .
Therefore, the total time complexity is:

T(n) = \Theta(n \log n)

This matches option C.

Final answer

Common trap

Assuming the inner loop always runs $O(n)$ times regardless of $i$ , which would erroneously give $O(n^2)$ .

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

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 38 of 65, printed as CS Q.38
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