3
$\begingroup$

I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$.

To determine the constant $C$ given by the relation $|T(n)| < C \cdot g(n)$, we take

$\qquad\displaystyle \lim_{n \to \infty} T(n)/g(n)$

which gives us

$\qquad\displaystyle \lim_{n \to \infty} (4+4n)/n = 4$.

However, in the answer sheet it say to take

$\qquad\displaystyle \lim_{n \to \infty}(4+4n)/n + 1 = 5$.

What is the purpose/reasoning for this $+ 1$ term, I haven't seen anything about before?

$\endgroup$
  • 2
    $\begingroup$ Also, your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Jan 28 '16 at 18:32
4
$\begingroup$

We want to find a $c$ such that $4+4n\le cn$ for all $n$ greater than or equal to some bound $N$. So we need a $c$ such that $(4+4n)/n \le c$, or $(4/n)+4\le c$. Now while it's true that $$ \lim_{n\rightarrow\infty}\frac{4}{n}+4=4 $$ we can't use $c=4$ since for all positive $n$ we have $(4/n)+4>4$. In other words, we need to pick $c$ to be some number larger than 4 and 5 is as good a choice as any in this case. There's nothing magical about picking a $c$ one greater than the limit; it's just one choice out of infinitely many.

$\endgroup$
  • $\begingroup$ Aha! Thank you so much. That is sort of what I was thinking, but I neglected to perform the "check" in that (4/n) + 4 > 4 for all n > 0 which would have indicated the problem. Again, thank you! $\endgroup$ – Chris Jan 29 '16 at 9:27

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.