Proof of the master thorem case with floors and b = 2

Question

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.

Answer 1

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.