Use the definition of big- notation to determine whether is .
To show that is , we would have to show that is and that is .
However, we can see that is not , as follows:
(This will be a proof by contradiction). Assume that is . This means that there exists a pair of positive constants such that, for all , we have that .
Since and we have that .
This means that we are assuming that for all .
It also means that we can safely divide both sides of the inequality by without changing it.
This gives that for all .
Since , this means that for all .
Whatever is, it’s just a constant, so is also just a constant. So this is saying that for all large values of , stays below the constant . This is a contradiction, so our initial hypothesis, that is , must have been false.
Since is not , cannot be .