time complexity

Question

 

 

Comments

A?

---

B) O( log²n) ??

---

B) O(n(logn)^2) ?

---

my doubt here,

suppose, the above code returns sum, then what would be sum approximate to? will it be same as its time complexity?

p.s: time complexity is no. of times "sum" evaluates.

---

I think it will be O(n(logn)²),

i for loop will run for logn times, j and k are dependent, so for, for j=n/2 k will run n/4 times....

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

hence logn*nlogn = O(n(logn)²).

---

@swapnil

How for j=n ,k will run n/2 can you please explain?

---

oh yeah this condition won't be there sorry as k will be equal to n, what about now? I edited it

---

given answer is b.

however am getting a

---

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?