Time complexity

Question

Answer 1

$T(n) = \sum_{i \text { is power of 2}}^n\sum_{j \text { is power of 2}}^i T(n/2) \\= \sum_{i \text { is power of 2}}^n \lg i T(n/2) \\= T(n/2) + 2T(n/2) + 3T(n/2) + \dots + \lg n T(n/2) \\= \frac{\lg n. (\lg n + 1)}{2} T(n/2) \\= O((\lg n)^2 T(n/2)) \\= (\lg n)^2 (\lg{n/2})^2 (\lg {n/4})^2 \dots 1 \\= (\lg n .(\lg n -1). (\lg n -2) . \dots 1)^2  \\=O\left( (\lg n)!^2\right) $

Comments

$\lg n * \lg (n+1) * T(n/2) = O((\lg n)^{2} * T(n/2)$)

But I am confused how

$(\lg n)^{2} * (\lg n/2)^{2} *(\lg n/4)^{2} *... *1 = 2*(\lg n +\lg (n/2) +\lg(n/4) + .. +1$)

Also the answer is O( lg lg n) or O((lg n)^2) . I mean just the representation is little wrong, but rests looks good.

---

@sir simply awesome procedure

but I think there is a miss logn(log n+1) /2 =O((log n)²)

even (log n)² and log²n are not same

(log n)² = (log n)*(log n)

(log²n) =log log n

right?

---

@srestha

Exactly I had tried to say the same in above comment. However, I am still confused how this step is done ?

$(\lg n)^{2} * (\lg n/2)^{2} *(\lg n/4)^{2} *... *1 = 2*(\lg n +\lg (n/2) +\lg(n/4) + .. +1$) 

Any idea?

---

yes, that was totally wrong.. See now..

Answer 2

O((log n)³)

1st for loop it will be (log n)

2nd for loop it will be again (log n)

R(n/2) it will again a log n iteration i.e. ((log n)³)

Comments

I don't know the answer but I was getting the same above recurrence. But is it correct? Because sum = sum+i; 

can also affect the time complexity, right?

---

No here qus is about time complexity not value.

---

Then I think your recurrence could be right !!