# Using Big $O,\Omega,\Theta$, how would you represent these equations?

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*}

• – D.W. Feb 8 '17 at 4:26
• $t(n)=O(2^{n^4})$, $g(n) = \Omega(\log\log n)$, $f(n)=\Theta(10n^5)$. – 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.