algorithms

Question

Comments

what should be its time complexity according to me it should be nloglogn

---

I think nlogn

---

there should be one correction in 1st for loop i.e $i=i/2$, otherwise code will run infinitely.

and TC should be $O(nlogn)$

---

why it should not be nloglogn plz explain

Answer 1

There is the dependency in the 3rd, inner loop to the variable p  so try with the normal approach.

for i = n                                                            | for i =  n / 2                                | ...............

j = 1, 2,3..........n-1                                           | j = 1, 2,..........n/2 -1                   | ............

each time p is incremented so                    | after completion of 2nd loop |....................

after completion of the 2nd loop  p = n     | p = n/2                                        |..................

Now 3rd loop will execute                            |Now 3rd loop will execute        |................

log (n) Base 3 time                                         | log (n/2) Base 3 time                 |..................

so finally if you add all   log(n) + log(n/2) + log(n / (2^2) ) + .....................log (n / (2 ^ log (n) Base 2) )

= O( (log (n) Base 3) * (log (n) Base 2) )

= O(log (n) ^ 2)

Comments

I am not getting how after completion of the 2nd loop p would be n or n/2 it should be nlogn na