Big Theta problem

I have two functions:

• f(n) = 2;
• g(n) = 10 ^ 100;

I have to justify if f(n) = BigTheta(g(n)) or not.

My guess is that f(n) is BigTheta(g(n)), since both functions are constants (wich means the functions are proportional), but a my te开发者_运维问答acher insists that I am wrong.

Am I right? Is there any way I could rest my case? Sorry if this sounds like a noob question! Thanks.

You are correct. Assuming you quoted the problem correct and there's no misunderstanding, your teacher is wrong if they said they are not theta-of-each-other.

Here's the definition:

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

Clearly |100^10|*k1 <= |2| <= |100^2|*k2 for constants k1=1/100^10 and k2=1 (for all x larger than any suitable cutoff value x_cutoff)

Without knowing the actual text of the exam problem though, and the exact text you wrote (or circled), there is no way we on the internet can know there isn't some sort of misreading of the problem. You should also note that you could still be wrong in your justification even though your answer is right.

For the record, not only is f(x) in the set BigTheta(g(x)), but g(x) is in the set BigTheta(f(x)). I think an equivalent definition is that the ratio of the two functions is bounded as x -> infinity (follows by dividing the Wikipedia definition by |g(x)| to get |f(x)|/|g(x)| < constant past some cutoff point), which may be an easier definition to think about (and more obvious to prove). It would also imply that BigTheta is a symmetric relation.

You now have the suitable tools to ask "why do you think I am wrong?" and then use math to determine which of you two are right; any misunderstanding should appear in the math, if not you'll have proved your point.

f(n) <= g(n) * 1
2    <= 10^100     for all n >= 0

Thus f(n) = O(g(n)).

f(n) >= g(n) * 2/(10^100)
2    >= 10^100 * 2/(10^100) = 2      for all n >= 0

And so f(n) = Ω(g(n)).

Both f(n)=O(g(n)) and f(n)=Ω(g(n)) imply f(n) = Θ(g(n)). Yes, you are right.