Gate CS-2017-2 Question Paper With Solutions

Q. 49 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 θ notation is:

(A) θ(n √n)

(B) θ(n²)

(C) θ(n log n)

(D) θ(n ² log n)

Answer: (C)

Explanation: