patternMinor
Justifying a claim in the proof of the master theorem
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!
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).
$$
$$
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.