Why are we not allowed to write Big-O notation in terms of fractions? Ex: O(n/2)

Question

For example, the average case for linear sort is described as O(n). But why is it not described as O(n/2), wouldn't it be this way because the average is the average times the program runs?

Answer 1

This is exactly the same statement because we have : $$O(n) = O\left(\frac{n}{2}\right)$$

Saying that a function $f$ is $O(n)$ means that there is an $N$ and some $K>0$ such that :

$$ \forall n > N, |f(n)| \leq Kn$$

So in particular we have .

$$\forall n > N, |f(n)| \leq (2K)\frac{n}{2}$$

We prefer to say $O(n)$ for simplicity.

Hence note that in general we have :

$$O(n) = O(Kn), \text{ for some } K > 0$$