GATE CSE 2017 Set 2 | Question: 38

Question

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

• A. $\Theta(n \sqrt{n})$
• B. $\Theta(n^2)$
• C. $\Theta(n \: \log n)$
• D. $\Theta(n^2 \log n)$

Comments

please verify @arjun sir

Answer 1

Consider for inner for loop : 

If the loop would have been:

for( j=1; j<n ; j= j+2)

Then the loop would have iterated n/2 times

So now in place of '2' we have 'i' : So my loop will iterate n/i times.

So this will vary with value of and we will get a series of : n + n/2 + n/3 + n/4........

=> n( 1 + 1/2 + 1/3.....)

=> nlogn

Answer 2

b

2 for....j varies 1...n

Answer 3

The first loop is independent, so it takes only n times, but the second loop is dependent on outer loop.so it takes o(logN)

so it takes o(NlogN).

opt c is correct