1
$\begingroup$

I am coming across two slightly different definitions of big-oh and need to prove that they are equivalent to each other:

Definition 1: f(n) = O(g(n)) if there exists constants c and N such that f(n) ≤ c g(n) for all n > N.

Definition 2: f(n) = O(g(n)) if there exists a constant c such f(n) ≤ c g(n) for all n≥1.

Intuitively I know that if we choose c large enough we can get rid of N like in definition 2. But how to prove that if definition 1 implies definition 2, and vice versa.

Assume g(n)>0 for all values of n (I need to prove this equality when it holds).

$\endgroup$
2
$\begingroup$

Assume definition $1$ holds. Then we have identified a $c$ that works for all but finitely many $n$. For each of the remaining finitely many $n$, we can check if $f(n)< cg(n)$ holds. If it does, then continue on. If it doesn’t, we can always find a $c’$ such that $f(n)<c’g(n)$ holds for that particular $n$. $c’>c$, so this will also hold for all the previously examined $n$. Iterate this through all the finite many $n$ and take the largest value of $c’$. Then definition $2$ holds.

The other direction is really easy. Try to think about it a bit more, because if you think about it in the right way it’ll be obvious.

$\endgroup$

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.