6

Assuming $n$ is a power of $2$, you have: $$ \sum_{i=0}^{\log n} \log \frac{n}{2^i} = \sum_{i=0}^{\log n} \left( \log n - i \right) = \sum_{i=0}^{\log n} i = \frac{(\log n)(\log n+1)}{2} = \Theta(\log^2 n). $$


4

You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again. To repeat, it is correct that "the cost $c_1=1$, $\Phi_0=0$", "$num_1=size_1=1$ $\implies$ $\Phi_1 = 2\cdot1-1 =1$" and " $\hat{c_1}=$ $c_1+\Phi_1-\Phi_0$ $=2$". It is incorrect to state that $\widehat c_i=...


1

The notations $f = \Omega(g)$ and $f \geq \Omega(g)$ are identical. In both cases, they mean that there exists a positive constant $C$ such that for large $n$, $f(n) \geq Cg(n)$. You can estimate the sum as follows: $$ \sum_{i=0}^n \sqrt{i} \log_2^2 i \geq \sum_{i=n/2}^n \sqrt{i} \log_2^2 i \geq \sum_{i=n/2}^n \sqrt{n/2} \log_2^2 (n/2) \geq \frac{n}{2} \cdot ...


Only top voted, non community-wiki answers of a minimum length are eligible