0
$\begingroup$

I have tried to write a "proof" for finding the range that c can be when analysing a function asymptotically. I am trying to understand the maths behind Big O and Big Omega. Can someone please take a look and let me know if I have gone about this the right way, have got the calculations correct, and have understood the terminology?

Many thanks

Big O

  • Consider the function:

$f(n) = 3n^2-100n+6$

  • To satisfy $O(n^2)$ we need to prove that $3n^2-100n + 6$ < $c * g(n^2)$
  • Let's say that
    • $n$0 $= 34$
  • Lets find the range of constants $c$ that can satisfy this bound

$3n^2 -100n + 6$ < $c * n^2$

$100n + 6$ < $c * n^2 + 3n^2$

$100n + 6$ < $n^2(c + 3)$

$\frac{100n + 6}{n^2}$ < $c - 3$

$100/n + 6/n^2 + 3$ < c

$c$$100/34 + 6/34^2 + 3$

  • Remove the $+ 3$ and round the fractions

$c$$3 + 0$

$c$$3$

  • We can say that for threshold $n$ > $34$, $c$ must be greater than or equal to 3 to be an upper bound of $O(n^2)$

Big ($\Omega$) Omega

  • Using the same function for $f(n)$ as in the example above

$f(n) = 3n^2 - 100n +6$

  • To satisfy $\Omega(n^2)$ we need to prove that $c * g(n^2)$ < $3n^2 - 100n + 6$
  • Let's say that
    • $n$0 $= 34$
  • Lets find the range of constants $c$ that can satisfy this bound

$c * n^2$ < $3n^2 -100n + 6$

$c$ < $\frac{3n^2 -100n + 6}{n^2}$

$c$ < $3 - 100/n + 6/n^2$

  • Remove the $+ 3$ and round the fractions

$c$ < $3 + 0$

$c$ < $3$

  • We can say that for threshold $n$ > $34$, $c$ must be less than 3 to be a lower bound of $\Omega(n^2)$
$\endgroup$
8
  • 1
    $\begingroup$ Please don't use images for text. $\endgroup$
    – Dominique
    Commented Jul 10 at 9:44
  • $\begingroup$ Updated to use markdown instead $\endgroup$ Commented Jul 10 at 10:06
  • $\begingroup$ In general, when you have a definition with something like "exists $c$" in it, you only need to demonstrate one value of $c$. I consider it a waste of effort to find the exact range of values $c$ "might" have in the definition. The effort should be spent instead on actually applying the definition to show that it is satisfied. $\endgroup$
    – David K
    Commented Jul 10 at 13:08
  • $\begingroup$ In fact, for $n_0=34$, it is necessary but not sufficient that $c < 3$. Values of $c$ very close to $3$ require larger values of $n_0$. I would just set $c=1$, in which case $n_0=34$ is OK but $n_0=100$ is just as good. $\endgroup$
    – David K
    Commented Jul 10 at 13:16
  • 1
    $\begingroup$ You wrote $g(n^2)$ when you should have written $n^2$ or $g(n)$. $\endgroup$
    – David K
    Commented Jul 10 at 13:21

1 Answer 1

1
$\begingroup$

Let me give you just a little disclaimer that the terminology is not entirely fixed. This is not the direct answer to your questions, but hopefully clears things up a bit. Indeed, some literature use the symbols $o,O$ and $\Omega$ with the relation $$f=O(g)$$ for example. Others utilize the set notation and the membership $\in$. I‘ll leave it to the Wikipedia article on Landau Notation to provide you with technicalities as it seems to be very good at it (also check other languages).

Now to parts of your question.

The definitions one usually takes are (shorthand):

\begin{align} f &= O(g) &:\Leftrightarrow \lim_{n\to \infty} \left| \frac{f(n)}{g(n)}\right| &< \infty \\ f &= o(g) &:\Leftrightarrow \lim_{n\to \infty} \left| \frac{f(n)}{g(n)}\right| &=0 \\ f &= \Omega(g) &:\Leftrightarrow \lim_{n\to \infty} \left| \frac{f(n)}{g(n)}\right| &= \infty \end{align} Caution: There is a limes superior here, but I again leave that to the article as it is sufficient for your cases to take the ordinary limit. Note, that the $n\to\infty$ must not be limit, but it can be any value (although you can reformulate it back to it).

Your case is (I ignore the absolute value here as $n>0$ and we are „close“ to infinity): \begin{equation} \lim_{n\to\infty} \frac{f(n)}{g(n)} = \lim_{n\to\infty} \frac{3n^2 - 100n + 6}{n^2} = 3 < \infty \end{equation} Hence, $f=O(g)$. You can reformulate the statement then in terms of bounds.

Feel free to criticize.

$\endgroup$
4
  • $\begingroup$ Hi dForga thanks for the answer. Can I take it then that my result of Big O c >= 3 and Big Omega c < 3 is correct? I think I follow your response but my maths isn't great and limiting function definitions have always confused me some what $\endgroup$ Commented Jul 10 at 13:10
  • $\begingroup$ The definition of $\Omega$ given here is more commonly given as a definition of the expression $f(x) = \omega(g(x))$. I've never seen $\Omega$ defined this way. $\endgroup$
    – David K
    Commented Jul 10 at 13:13
  • $\begingroup$ @PumpkinBreath Yes, the $c\geq 3$ is then this limit. So, you did great. For the limit, recall that you can take individual limits if each exist, that is you can factor out the $n^(2)$ and see that the new numerator and demoninator have an existing limit. $\endgroup$
    – dForga
    Commented Jul 10 at 16:22
  • $\begingroup$ @DavidK Yes, this can be the case. I have seen that one too. As far as I know is the literatur not fully standardized regarding some aspects of notation. I‘d therefore take the practical point of view here: As long as it is defined before, it should not be a problem. $\endgroup$
    – dForga
    Commented Jul 10 at 20:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .