2
$\begingroup$

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.

1 Answers 1

3

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.