0
$\begingroup$

I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so long as it is a real number and less than the right side? For instance, is the following valid: $$n^2/4 + 1/2 \leq c\cdot n^2\,,$$

when $c= 1$ and $n=1$: $$3/4 \leq 1\,.$$

$\endgroup$
  • 1
    $\begingroup$ What part of what definition have you read that makes you think the left side might have to be bigger than 1? $\endgroup$ – David Richerby Feb 25 '16 at 5:21
  • $\begingroup$ Not necessarily bigger than one, but greater than or equal to one. I was just thinking in terms of how a program would operate. The program I was looking at won't perform any work unless the $n$ input is high enough to have the left side greater than or equal to 1. $\endgroup$ – TacoB0t Feb 25 '16 at 5:25
1
$\begingroup$

"The Big-O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions."-Wikipedia

If you see the formal definition, then the only restriction is that the domain of functions must be $\mathbb{R}$. Hence, by definition the range of the functions can at least be any vector space. In the most common use in CS, the range of the functions is also taken to be $\mathbb{R}^+$.

To answer your question, by definition, the left side can be any real positive value.

$\endgroup$
  • $\begingroup$ So this could also have been a negative on the left side and it would still hold? $\endgroup$ – TacoB0t Feb 25 '16 at 5:47
1
$\begingroup$

No such restriction is required. To satisfy Big-O notation you have to find out a constant c > 0 and $n_0$ such that $f(n) \le c g(n)$ for all $n \ge n_0$. The only assumption is $f$ and $g$ are functions such that $f, \ g : N \rightarrow R^+$.

$\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.