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


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!

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

1 Answer 1


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

  • $\begingroup$ Ah makes sense thanks so much! $\endgroup$
    – random0620
    Commented Feb 20, 2021 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.