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

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

https://math.stackexchange.com/questions/5035/is-there-any-formula-for-the-series-1-frac12-frac13-cdots-frac-1-n

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.

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 !!!!