3
$\begingroup$

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.

enter image description here

My argument is as follows:

Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$.

$$g(n)=\sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i)$$

Now by the definition of big O, we have that $\exists c\in\mathbb{R}, N'\in \mathbb{R }$ such that $\forall n/b^j>N'$, we have that $$f(n/b^j)<c(n/b^j)^{\log_b{a}-\epsilon}$$

This implies that $\forall n>N'b^{\log_bn-1}$

$$g(n)= \sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i) \leq \sum_{i=0}^{\log_{b}(n)-1}a^ic(n/b^i)^{\log_b{a}-\epsilon} \leq c\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon} $$

Which implies that $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$ with $M=c$ and $N=N'b^{\log_bn-1}$.

Have I found the correct $c$ and $N$ to prove this claim for the upper bound of $g(n)$ and is this proof valid? Thanks!

$\endgroup$
5
  • $\begingroup$ For red: just substitute $n$ with $\frac{n}{b^j}$. $\endgroup$ – zkutch Feb 20 at 19:04
  • $\begingroup$ @zkutch Wouldn't I also have to substitute it in the LHS g(n) as well? $\endgroup$ – s_kirkiles Feb 20 at 19:05
  • $\begingroup$ No. It is used only for $f$ in right hand. $\endgroup$ – zkutch Feb 20 at 19:06
  • $\begingroup$ But the inequality only holds past some N. Isnt that assuming it holds for all n? @zkutch $\endgroup$ – s_kirkiles Feb 20 at 19:42
  • $\begingroup$ Related: cs.stackexchange.com/questions/112779/… $\endgroup$ – s_kirkiles Feb 20 at 20:37
4
$\begingroup$

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the maximum value of $f(n)/n^{\log_b a - \epsilon}$ over all positive integers $n < N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq \max(M,C) n^{\log_b a - \epsilon}$ holds for all integer $n \geq 1$. Therefore $$ g(n) = \sum_{j=0}^{\log_b n-1} a^j f(n/b^j) \leq \max(M,C) \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} = O\left( \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} \right). $$

$\endgroup$
1
  • $\begingroup$ Ah makes sense thanks so much! $\endgroup$ – s_kirkiles Feb 20 at 20:42

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.