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)$

Answer 1

Inner for loop is dependent on $i$, so for each $i$ we have to check no of times inner loop operating..

It ll be something like

 $\frac{n-1}{1}+\frac{n-1}{2}+\frac{n-1}{3}+...........+\frac{n-1}{n-1}+1$

$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+......+\frac{n}{n-1}-\log(n-1)$

$n\{{\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+.....+\frac{1}{n-1}}\} - \log(n-1)$

$n\log(n-1)-\log(n-1)$

$n\log(n-1)$

$n\log n$

Correct Answer: $C$

Comments

anyone please explain how :

1/1+1/2+1/3+......+1/n becomes logn

thank you!

---

Integration of 1/x is logx ....

---

I dont think Integral works for discrete things ........

Answer 2

$i=1 \rightarrow j : 1 ..2..3..4..5..6..7..8..9..10......approx (n times)$

$i=2 \rightarrow j : 1 ..3..5..7..9..11..13.................approx (n/2 times)$

$i=3 \rightarrow j : 1 ..4..7..10..13..14..17..............approx (n/3 times)$

$T(n)= n + n/2 + (n/3) + (n/4)+ (n/5) + (n/6)......... =\Theta (nlogn)$ {best option}

Comments

how this summation become log n,  source  : https://www.quora.com/What-is-the-sum-of-the-series-1+-1-2-+-1-3-+-1-4-+-1-5-up-to-infinity-How-can-it-be-calculated
Edit : solved : its not approaching infinite rather going to n

---

here inner loop increment condition depends on the outer loop, so you can’t calculate them individually as you do when they are independent. Here you have to unravel the loop to find the time complexity.

---

@Divyan this is harmonic GP sum which is logn

Answer 3

Ans) c

First time inner loop run -----n times

2nd   time    ''           ''      ''----n/2 times

Then,n/3,n/4....till  n/n=1 time

Total=n+n/2+n/3+n/4+n/5+......+n/n=n(1+1/2+1/3+...+1/n)=⊝(nlogn) (approx)

Answer 4

for i=1;j will run=1to n=n tym

​​​​​​i=2;j will run =1ton=n/2 tyms

i=3;j will run 1to n=n/3 tyms

i=4;j will run 1 to n=n/4 tyms

...so on i=n; j will run 1to n=1 tym;

therefore j will run in total=(n+n/2+n/3+n/4+..........1)=n(1+1/2+1/3+1/4.......)=nθ(log n)=θ(nlogn)

option c

Comments

U hav described same as other answers !!!!

Answer 5

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 6

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