# Big-O Justification Question

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

• What part of what definition have you read that makes you think the left side might have to be bigger than 1? – David Richerby Feb 25 '16 at 5:21
• 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. – TacoB0t Feb 25 '16 at 5:25

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}^+$.
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^+$.