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

nice answer ...

---

why can't the answer be D? I'll first find the complexity of the inner loop as nlogn, and then multiply it with the complexity of the outer loop i.e n, and the answer turns out to be D?

---

I think as we are calculating  the complexity of the inner loop using the values of i, we are already taking outer loop under consideration. This is the reason the answer is nlogn but not n^2lgn.

---

How 1 + 1/2 + 1/3 + 1/4 +1/5 + .................. + 1/n being logn??

can anybody explain please?

---

We can do this using integration :-

---

Integration is for continuous function.

When you are integrating it from 1 to n then you are taking every point between 1 and n e.g. 1.01,1.02 and infinite points.

But here we have only 1,2,3,4,......... n

---

Its a summation of n term harmonic series :-

Refer:- https://en.wikipedia.org/wiki/Harmonic_number

---

The outer loop has no use here except calculating the value of the inner loop.

---

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