-1
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – codeR
    Commented Jun 25 at 10:32

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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. enter image description here 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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.