snippetMinor
How to prove an implication about an upper bound mentioned in the proof of master theorem?
Viewed 0 times
boundthementionedprovemasterimplicationabouttheoremhowupper
Problem
How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"?
For given constant b and j, the implication in green makes sense. If the upper bound of j was fixed, the equation 4.23 follows directly. However, when n increases, the upper bound of j also increases, though is slower. It is where I find difficult to prove there always exists a value m > 0 such that for all n >= m, equation 4.23 is true.
For given constant b and j, the implication in green makes sense. If the upper bound of j was fixed, the equation 4.23 follows directly. However, when n increases, the upper bound of j also increases, though is slower. It is where I find difficult to prove there always exists a value m > 0 such that for all n >= m, equation 4.23 is true.
Solution
The statement $f = O(h)$ just states that there exists a constant $C>0$ such that $f(N) \leq Ch(N)$ for all $N$ (some variants have this hold only for large enough $N$, but in most cases there is no difference). In your case, $f(N) \leq CN^{\log_b a-\epsilon}$ for all $N$. This holds for $N = n/b^j$ in particular, and implies that
$$
g(n) \leq C \sum_{j=0}^{\log_b n-1} a^j (n/b_j)^{\log_b a-\epsilon}.
$$
As for the two different definitions of big O: suppose that $f(N) \leq CN^{\log_b a-\epsilon}$ holds only for $N \geq N_0$, and let $M = \max(C,f(1),\ldots,f(N_0))$. Then $f(N) \leq MN^{\log_b a-\epsilon}$.
$$
g(n) \leq C \sum_{j=0}^{\log_b n-1} a^j (n/b_j)^{\log_b a-\epsilon}.
$$
As for the two different definitions of big O: suppose that $f(N) \leq CN^{\log_b a-\epsilon}$ holds only for $N \geq N_0$, and let $M = \max(C,f(1),\ldots,f(N_0))$. Then $f(N) \leq MN^{\log_b a-\epsilon}$.
Context
StackExchange Computer Science Q#112779, answer score: 2
Revisions (0)
No revisions yet.