patternMinor
Why add a +1 to the constant proving an O(n) bound?
Viewed 0 times
provingwhytheboundconstantadd
Problem
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?
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?
Solution
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.
$$
\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.
Context
StackExchange Computer Science Q#52405, answer score: 4
Revisions (0)
No revisions yet.