time complexity

Question

 

 

Consider the following piece of code
```
for(i=1; i {
for(j=n; j>0; j=2)
{
for(k=j; k {
sum+=(i+j*k);
}
}
}
```

The time complexity of above code $\qquad$
a) $O(n \log n)$
b) $\mathrm{O}\left(\mathrm{n}(\log )^{2}\right)$
c) O(nloglogn)
d) O(loglogn)

Comments

his is nothing but n/4+n/8 .. ........ + n/2^k+1 , now taking n/4 outside it will be O(nlogn).

@swapnil naik

even i was getting the same but just see this,

i goes for logn times right,

now we come to j 

when j=n/2 , k goes n/4 times;

when j=n/4 , k goes n/8 times;

when j=n/8 , k goes n/16 times;

................and so on logn times;

hence we get ------> n/4 + n/8 + n/16 + ..........(logn)terms

taking n/4 common

=n/4[ 1+ 1/2+ 1/4+ 1/8 .............logn terms]

=n/4(n/n-1)

=n/4

approx n

therefore total time complexity becomes = nlogn?

therefore option a is correct na.......how b?

 

where am i wrong??

---

the complexity of this portion is O(n) .

am i right?

---

See

1st For loop will run logn times for which 2nd for loop run again logn times for which 3rd for loop will run n/2 times as it will not run for ist time bcs condition will not get satisfy so overall this may be the scenioro :logn[logn(n/2) ] =O(n (logn) ^2)

Answer 1

O{n(logn^2)}

Answer 2

For purpose of solving I am assuming that n=2$^{c}$ where c>1

1) outer loop or i$^{th}$ loop will execute (log n) times

2) middle loop or j$^{th}$ loop will execute (log n)+1 times

3) now for last loop or K$^{th}$ loop will run for :

$\sum_{k=1}^{log n+1}  \left ( \frac{n}{2}+1-k \right )$

 

Eg:

for n=8, 1$^{st}$ loop will execute 3 times

now 2$^{nd}$ will  execute  (log n +1) i.e 4 times

and 3$^{rd}$ loop will execute 10 times as per formula

 

we can simplify $\sum_{k=1}^{log n+1}  \left ( \frac{n}{2}+1-k \right )$ as = $\frac{n}{2} - \left ( 1+2+3...log n \right )$

since -(1+2+3...log n )  is negligible we will omit in result

so final answer is (log n)*((log n)+1)*($\frac{n}{2}$)= O(n* (log n)$^{2}$)

 Answer is B

Comments

3) now for last loop or Kth loop will run for :

how you got n/2+1-k ? How you derive this?