1
$\begingroup$

This question is related to my previous one.

Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b > 1$ and $f(n) = \Theta(n^{\log_ba})$. Then $T(n) = n^{\log_ba} + \sum_{j=0}^{\lfloor \log_b n \rfloor - 1} a^{j}f(n_j) = n^{\log_ba} + g(n)$. It should be proved that $g(n) = \Omega(n^{\log_ba}logn)$.

It's seems not to be a difficult problem as there is the proof of the similar one (for the upper bound and a presence of the ceiling operation in recursive calls) in the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein. But I found it becomes more difficult to deal with if $b=2$:

$n_j = \begin{cases} n, & \text{if j = 0} \\ \lfloor n_{j-1}/b \rfloor, & \text{if j > 0} \end{cases}$

$n_j \geq n/b^{j} - \sum_{i=0}^{j-1}1/b^{i} \geq n/b^{j} - \sum_{i=0}^{\infty}1/b^{i} = n/b^{j} - b/(b-1)$

By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum_{j=0}^{\lfloor \log_b n \rfloor - 1}a^{j}(\frac{n}{b^{j}} - \frac{b}{b-1})^{log_ba} =$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{j}}{n}\frac{b}{b-1})^{log_ba} \geq$ //where $\frac{b^{j}}{n} \le 1$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor -1 }}{n}\frac{b}{b-1})^{log_ba} = $

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor }}{n}\frac{1}{b-1})^{log_ba} \geq$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{1}{b-1})^{log_ba}$

Note iff $b = 2$ than $(1-\frac{1}{b-1})^{log_ba} = 0$ and can not be denoted as an allowable constant in terms of $\Omega$ (it must be a positive one).

I tried to prove that particular case in another way, if $n_j \geq \frac{n}{2^{j}} - (2 - \frac{1}{2^{j-1}})$ (it is the sum of the geometric progression without the limit) but finally failed because of the same issue.

$\endgroup$
1
$\begingroup$

In fact, let $b=1.5$, we will have $(1-\frac{1}{b-1})<0$, in which case $(1-\frac{1}{b-1})^{\log_ba}$ does not even make much sense!

The problem can be traced to when the following too-relaxing relaxation was made.

$$1-\frac{b^{j}}{n}\frac{b}{b-1} \geq 1-\frac{b^{\lfloor \log_bn \rfloor -1 }}{n}\frac{b}{b-1}$$


Can we find $\Theta(\log n)$ times when the left side is greater than, for example, $\frac12$? That should be enough to generate the factor $\log n$ needed.

Let us solve the following equation for the index $j$. $$1-\frac{b^{j}}{n}\frac{b}{b-1} \gt \frac12$$ We get $$j \lt \log_b\left(\frac{n(b-1)}{2b}\right)=\log_bn-\log_b\frac{2b}{b-1}=\frac{\log n}{\log b}-c_0$$ where constant $c_0=\log_b\frac{2b}{b-1}$.

The above should be enough to set you moving for a complete proof, although there might be a couple of other minor technicalities ahead.

$\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.