# Thread: Determining the Truth of Statements

1. ## Determining the Truth of Statements

Hey everyone. I've been having a lot of difficulty in my discrete math class and was hoping you could help me out. I can't seem to figure out how to go about solving problems containing Big-Theta, Big-O and Big-Omega notation. I have a couple of sample questions for what we are doing in my course, and any help with this would be greatly appreciated.

1) n^2 / 3 + 33n is Big-Omega(n)
2) n^3 / 58 - 7n^2 is Big-Theta(n2)
3) 18n^2 - 27n + 47 is Big-O(n3).

2. Originally Posted by HelloJoe
Hey everyone. I've been having a lot of difficulty in my discrete math class and was hoping you could help me out. I can't seem to figure out how to go about solving problems containing Big-Theta, Big-O and Big-Omega notation. I have a couple of sample questions for what we are doing in my course, and any help with this would be greatly appreciated.

1) n^2 / 3 + 33n is Big-Omega(n)
2) n^3 / 58 - 7n^2 is Big-Theta(n2)
3) 18n^2 - 27n + 47 is Big-O(n3).
All you have to remember is that $\displaystyle \Omega$ is the order at LEAST n.

When you look at it this way, here is a good list to know, in order from smallest to largest rate of growth:

$\displaystyle c$ (c is some constant)

$\displaystyle \log_2{n}$ (logarithmic)

$\displaystyle n$ (linear)

$\displaystyle n \log_2{n}$ (logarithmic)

$\displaystyle n^2$

$\displaystyle n^3$

.

.

.

$\displaystyle n^n$

$\displaystyle 2^n$

$\displaystyle 3^n$

.

.

.

$\displaystyle m^n$

If you are looking for the LEAST order, you look for the smallest in this list and that entire function takes that order.

If you are looking for the HIGHEST order, you look for the largest in this list and that entire function takes that order.

I'm sure you can get through this now.