1
$\begingroup$

I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b > 1$, $n$ is an exact power of $b$ and $f(n)$ is an asymptotically positive function, to prove that if $f(n) = \Theta(n^{\log_ba}lg^{k}n)$, where $k\geq0$, then $T(n)=\Theta(n^{\log_ba}lg^{k+1}n)$.

Since $T(n) = n^{\log_ba} + g(n)$ where $g(n) = \sum_{j=0}^{\log_b n - 1} a^{j}f(n/b^{j})$, I decided to consider the $g(n)$ function at the first. And I have shown $g(n) = O(n^{\log_ba}lg^{k+1}n)$ already (I think so).

But the doing the proof $g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$ became a challenge for me.

Below is my research (with the simplified assumption $k$ is an integer). By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum_{j=0}^{\log_b n - 1} a^{j}(n/b^{j})^{log_ba}log^{k}(n/b^{j}) =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1} log^{k}(n/b^{j}) =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}(logn - logb^{j})^{k} =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}log^{k-i}n(-logb^{j})^{i} =$

$cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}(-logb^{j}/logn)^{i} =$

$cn^{\log_ba}log^{k}n \biggl(log_bn + \sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(-logb^{j}/logn)^{i} \biggr) \geq$

$c'n^{\log_ba}log^{k+1}n - cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(logb^{j}/logn)^{i} =$

$A(n) - B(n) = \Theta(n^{\log_ba}lg^{k+1}n) - B(n)$

Actually I am stuck with it. I can not show that $B(n)$ grows slower than $A(n)$. For instance, since $(logb^{j}/logn)^{i} \le 1$ we are able to enhance our $\geq$ condition by the substitution $B(n)$ to some fucntion $B'(n)$ with the sums of binominal coefficients only. But then finally $B'(n)$ has $n^{\log_ba}log^{k+1}n$.

So how to prove $g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$ ?

$\endgroup$
1
$\begingroup$

All we need to prove is the following, where $b>1, k\ge 0$ and $k$ may or may not be an integer. $$\sum_{j=0}^{\lfloor\log_b n\rfloor} \left(\log_b\left(\frac n{b^{j}}\right)\right)^k=\Omega((\log_b n)^{k+1})$$

In order to show the idea of the proof clearly, assume that $n = b^m$. The above estimate is $$\sum_{j=0}^{m} (m-j)^k=\Omega(m^{k+1})$$

Here is the proof.

$$\sum_{j=0}^{m} (m-j)^k=\sum_{i=1}^m i^k\ge\sum_{i=1}^m \int_{i-1}^{i} u^k du=\int_{0}^{m} u^k du = \left.\frac{u^{k+1}}{k+1}\right |^m_0= \frac{m^{k+1}}{k+1} $$

$\endgroup$

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.