How would you write the following equations in $O,\Omega,\Theta$ notation? $$ \begin{align*} t(n) &= 4n^4 + 3n^5 + 3n^6 \\ g(n) &= 2n^6 + 5\log n \\ f(n) &= 50n^5 \end{align*} $$

  • $\begingroup$ cs.stackexchange.com/q/824/755, $\endgroup$ – D.W. Feb 8 '17 at 4:26
  • $\begingroup$ I know there's a guide, and I've read it, but still can't get to an answer. Please help $\endgroup$ – Luna Debb Feb 8 '17 at 4:28
  • 1
    $\begingroup$ $t(n)=O(2^{n^4})$, $g(n) = \Omega(\log\log n)$, $f(n)=\Theta(10n^5)$. $\endgroup$ – David Richerby Feb 8 '17 at 11:04

Let's visit the basic definition of the asymptotic notations you have written. In computer science, these notations are mostly used to study the growth of the runtime of an algorithm with the input size.

In Big-O notation, we write $$f(x) = O(g(x))$$ if and only if there exists a positive real number M and a real number $x_0$ such that $$|f(x)| \leq M |g(x)| \text{ } \forall x \geq x_0 $$

Similarly, we have

$f(n)= \Theta (g(n)) \text{ iff } k_{1}\cdot g(n)\leq f(n)\leq k_{2}\cdot g(n) \text{ for some positive } k1, k2$ and
$f(n)=\Omega (g(n)) \text{ iff } f(n)\geq k\cdot g(n) \text{ for some positive } k$

Now having the definitions in hand, your questions can be answered quickly.

$t(n) = 4n^4+3n^5+3n^6 \leq 10n^6 \text{ ( since } n^4 \leq n^6 \text{ and } n^5 \leq n^6 \text{ ) }$ $ = O(n^6) \text{ from the defintion } $

Also, $ t(n) \geq 3n^6 => 3n^6 \leq t(n) \leq 10n^6 => t(n) = \theta(n^6) $

and, $ t(n) \geq 3n^6 => t(n) = \Omega(n^6) $

Now you can use the same logic for the other two to get,

$ g(n) = O(n^6) = \theta(n^6) = \Omega(n^6) $
$ f(n) = O(n^5) = \theta(n^5) = \Omega(n^5) $

Note: If you look closely at the definitions of the $ O, \theta, \Omega$ notations, you will see that there can be many possible answers for your questions. For example,

$ f(n) = 50n^5 \geq n^4 \geq n^3 \geq n^2 \geq log n .. $
$ => f(n) = \Omega(n^4) = \Omega(n^3) = \Omega(n^2) = \Omega(log n) $

If you are really interested in complexity analysis and asymptotics, have a look at https://en.wikipedia.org/wiki/Big_O_notation#Equals_sign. It discusses the nuances of the notation and the notational abuse in using equality in my answer for simplicity.

| cite | improve this answer | |

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.