# Why add a +1 to the constant proving an O(n) bound?

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?

• 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!
– Raphael
Jan 28 '16 at 18:32

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.