I was doing some algorithm analyses, and I end up with a expression like $\sum_{k=0}^{\log_2n}(\log_2(n/2^k))^p$, where p is a fixed positive integer. I could change it to like $\sum_{i=0}^p(k-i)^p$, but how to compute it and obtain a $\Theta$() notation?

Thanks a lot.


We have that $$(\log n)^p + (\log \frac{n}{2})^p + \dots \le (\log n)^p \log n = \log^{p+1} n$$

We also have that

$$(\log n)^p + (\log \frac{n}{2})^p + \dots \ge \frac{(\log \sqrt{n})^p \log n}{2} = \frac{\log^{p+1} n}{2^{p+1}} $$

(by considering the first $\frac{\log n}{2}$ terms)

Since $p$ is fixed, the expression you have is $\Theta(\log^{p+1} n)$

(Of course, there has been a slight abuse of notation, as we need to consider the integer part of $\log n$, $\frac{\log n}{2}$ etc), but the result will be the same.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.