# O-notation confusion

I'm reading CLRS and I can't understand this part: in n-100<=c why we can't choose 101 for n (and more) and any value of c that's >=1?

• Please do not post images as the main question, as it would make the job search engines (to point to this post in the future) difficult, if not impossible. Commented Jun 25 at 10:32

The definition of big-oh notation requires that for $$f(n) \in O(g(n))$$ there exists some positive constant $$c$$ such that for all $$n \ge n_0 \ge 0$$ the relation $$f(n) \le cg(n)$$ must hold.

Notice that there is no upper bound on $$n$$. But in the above case, we have $$n \le c + 100$$. Whatever arbitrary large value you may choose for $$c$$, this still remains a finite and fixed upper bound for $$n$$, and thus directly contradicts the definition.

You don't choose values for $$n$$, you choose values only for $$n_0$$ and $$c$$. Assuming this is what you meant, then the inequality becomes \begin{align*} n - 100 &\le 1 & \forall n \ge 101 \\ n &\le 101 & \forall n \ge 101 \end{align*}

Which is false for $$n=102$$

Let c = 1 and n = 101.

...this inequality does not hold for any value of $$n > c + 100$$

$$101$$ is not $$~> 1 + 100$$.
If $$n$$ is any larger, $$n-100\le c$$ doesn't work out.
If even $$n=102$$, we would have $$2 \le 1$$.

Their algebra checks out. Consider $$n-100\le c$$ can be solved as $$n \le c + 100$$ so if $$n>c+100$$, the previous expression would be false.

Intuitively, they're trying to express that you should be able to pick a $$c$$ such that for big values of $$n$$, the expression belongs to the class $$O(n^3)$$ and not $$O(n^2)$$. That for a $$c$$, all big values of $$n$$ satisfy $$n^3 - 100n^2 \le cn^3$$. Generally, big O notation is concerned with large values of $$n$$; how things scale.

It's easy to appreciate from a graph. Notice that the expression (in red) looks more like $$-n^2$$ (green) at first. But for big values of $$n$$, it looks a lot more like $$n^3$$ (blue).