Will the definition of big $O$ be equivalent to the one where we exchange the $n \ge N$ condition with $\forall n$

24 Views Asked by At

If we delete from the big $O$ definition the "$\exists N > 0$ such that $\forall n \ge N$" part and leave only the "$\forall n$" will the new definition be equivalent to the original one for $N \to N$ and for $N \to R_{>0}$?

Original: $ O(g(n)) = ${$f (n) $: there exist positive constants $c$ and $n_0$ such that $0≤ f (n) ≤cg(n)$ for all $n ≥ n_0$}.

The new one: $ O(g(n)) = ${$f (n) $: there exist positive constant $c$ such that $0≤ f (n) ≤cg(n)$ for all $n ≥ 0$}.

My thoughts is that the new definition is not equivalent to the original one. I think, so because while for all $n$ for which the original proposition is true the new is also true, that is original $\to$ new follows, however it is not true that the same works in the reverse direction. Because there would be such $n < n_0$ for which the new definition will be true and at the same time the old one will not be, that is new $\not \to $ original.

However, in this case, if the logic is not faulty why should the $N \to N$ or $N \to R_{>0}$ parts make any difference?

1

There are 1 best solutions below

3
On BEST ANSWER

Let $f(n)=42$ and $g(n)=(n-17)^2$. Do the two definitions agree on whether or not $f(n)\in O(g(n))$?