1
$\begingroup$

We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c_1, c_2$ > 0 and $n_0$ such that 0 $\leq$ $c_1$g(n) $\leq$ f(n) $\leq$ $c_2$g(n) for all n > $n_0$}.

I found an illustration of this statement on Wikipedia, but I cannot figure out what exactly point $n_0$ means. How should we choose $n_0$ in practice? If I found, how should I use it?

$\endgroup$
2
$\begingroup$

It just means that the condition $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ only needs to hold for large enough integers.

This allows you to ignore all integers that are smaller than $n_0$ so you can just pick $n_0$ as large as needed for the inequalities to hold.

Notice that you do not need to pick $n_0$ as the smallest integer with that property, so you might as well pick one that makes proving the inequalities as easy as possible.

$\endgroup$
2
  • $\begingroup$ That makes sense, since not all values of n hold the statement above due to constants. Thank you! $\endgroup$ Jul 8 at 10:37
  • 1
    $\begingroup$ For strictly positive functions on the integers domain (such as functions representing running time), the smallest $n_0$ is actually 0: just choose a constant $c$ big enough to overcome the first $n_0$ values. So I think its important to also note that $n_0$ isn't always needed, and when it isn't it can just be ommited altogether :) (to save your precious time from writing that $n_0$) $\endgroup$
    – nir shahar
    Jul 8 at 11:07

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.