Time complexity of the given program.

Question

Consider the following program segment:
```
count = 0;
for 1-1 to n
{
M= floor(n/1);
for j-1 to m
count = count + 1;
}
```

The order of magnitude of the program segment is

• A. $\theta(n \log n)$
  
• B. $O(n)$
  
• C. $\mathrm{O}(\mathrm{n}$ sqrt(n))
  
• D. None
  A B C D
  Your answer is incorrect.
  
  The correct answer is: A

Comments

it will be

n + n/2 + n/3 + n/4 + n/5........n/n

n(1 + 1/2 + 1/3 + 1/4.....1/n) = n*O(logn) = O(nlogn)

---

$\sum_{i=1}^{n} \sum_{j=1}^{floor(n/i)}1$

$=\sum_{i=1}^{n} floor(n/i)-1+1$

$=\Theta{(nlogn)}$

Answer 1

So, option A.

Comments

How is (1 + 1/2 + 1/3 + ... + 1/n) = O(logn)??

Can you please provide any proof for this??

---

see this,

https://stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series

---

Can we take  j= n-1,n-2,n-3,n-4....n-n instead of j= n/1..n/2..n/n?? @Pinaki Dash

---

The no. of times 2nd 'for loop' runs is determined by the value of 'm' as j runs from  1 to m. And the value of m changes for each iteration of 1st 'for loop' because of m=n/i as i changes in each iteration of the 1st loop. That's why we write it as loop runs for n/1+n/2+n/3.... times

Had it been like 'm=n-i' in place of 'm=n/i', then we would have written that the loop runs for (n-1)+(n-2)+(n-3)+....+(n-n) times.

---

thanks