How to determine if a function f is in theta(g)

Full disclosure: This is a homework proble开发者_开发技巧m. I'm honestly freaking out a little that it's evaded me for so long when it seems so simple.

Okay, the question is, f(n) = n^2*log(n), g(n) = n^2.1. Is f in theta(g)?

I just need to come up with constants c₁, c₂ so that past a certain n₀, f(n) <= c₁g(n) <= c₂f(n). But I'm not even sure f is in theta(g) at all. I'm that confused.

From what I remember, to prove f(n) is in theta(g(n)), you can take two different approaches:

1. Prove f is in O(g) and prove g is in O(f).

2. Prove f is in O(g) and prove f is in BigOmega(g).

First note the wording. "Is f in theta(g)". This means they want you to first make an educated guess on whether or not it is true.

Counter question: is theta(n) the same as theta(n * log(n))? We know the answer to that one... no they are not (for otherwise comparison based sorting would be linear for instance). What does this suggest on your question?

To prove the claim, follow the other answer by MahlerFive. For completeness, to attempt to disprove the claim, suppose an enemy has come up with constants c1 and c2. Now our goal is to show that despite what constants the enemy has come up (that is, for all c1 and c2) there are no n0 fulfilling the bound. In other words, show that there is no way you can choose c1 and c2. The trick in your case is probably centered around the log(n) factor in the f function. log(n) is monotonically increasing suggesting we can make that factor arbitrarily big by plugging in a larger n-value.

I hope this gets you going a little while still having the satisfaction of solving the problem yourself. If I am totally wrong, I am sure other readers will correct me.