0

As far as i know the definitions are:

$f(n)$ is $O(g(n))$ iff there exists $ c > 0, n_{0} $ such that $f(n) \le c \times g(n)$ holds for all $n \ge n_{0}$

$f(n)$ is $o(g(n))$ iff there exists $ c, n_{0} $ such that $f(n) \lt c \times g(n)$ holds for all $ c > 0 $ and $n \ge n_{0}$, where $n$ can depend on $c$, for example $n_{0} = c /2$

$f(n)$ is $\theta(g(n))$ iff there exists $ c', c'' > 0, n_{0} $ such that $f(n) \le c' \times g(n)$ and $f(n) \ge c'' \times g(n)$ holds for all $n \ge n_{0}$

$f(n)$ is $\Omega(g(n))$ iff there exists $ c > 0, n_{0}$, such that $f(n) \ge c \times g(n)$ holds for all $n \ge n_{0}$

The part that I am not sure about is the correct ranges to choose $c, n$ from. Are the definitions I wrote correct?

August
  • 99
  • @Winther yes, that's what i mean, however I am not sure how would I word it different – August May 20 '18 at 14:37
  • I presume you are trying to put those formal definitions into words. But your order appears to be backwards. There exists a pair or pairs $c,n_0$ that make the inequality e.g. $f(n)\leq c\cdot g(n)$ hold. Not the other way around. – String May 20 '18 at 14:55
  • @String if you disregard that, are the pairs c,n chosen correctly ? is c supposed to be c > 0 for every definition ? – August May 20 '18 at 15:22
  • Yes, $c>0$ is indeed correct. And of course $n\geq n_0$ since the latter is indeed the asymptotic idea "whenever $n$ is big enough". – String May 20 '18 at 15:53

0 Answers0