HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Justifying a claim in the proof of the master theorem

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theclaimmastertheoremjustifyingproof

Problem

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.

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)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!

Solution

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

Context

StackExchange Computer Science Q#135707, answer score: 4

Revisions (0)

No revisions yet.