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

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