enter image description here

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.

  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – dkaeae Aug 16 '19 at 12:56

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

| cite | improve this answer | |
  • $\begingroup$ I am using the book, amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844, which defines the big-o notation as the variant you mentioned, and so I cannot assume the existence of constant C for all N as you suggest. My concern is when j grows as n grows, what is value N0 such that the inequality holds for all N >= N0. $\endgroup$ – Hiep Aug 16 '19 at 1:27
  • $\begingroup$ In the last paragraph I explain why $N_0$ isn’t necessary in this case. $\endgroup$ – Yuval Filmus Aug 16 '19 at 3:08

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.