Proving that a function f(n) belongs to a Big-Theta(g(n))

views:

273

answers:

Proving that a function f(n) belongs to a Big-Theta(g(n))

Its a exercise that ask to indicate the class Big-Theta(g(n)) the functions belongs to and to prove the assertion.

In this case f(n) = (n^2+1)^10

By definition f(n) E Big-Theta(g(n)) <=> c1*g(n) < f(n) < c2*g(n), where c1 and c2 are two constants.

I know that for this specific f(n) the Big-Theta is g(n^20) but I don't know who to prove it properly. I guess I need to manipulate this inequality but I don't know how

+1 A:

Michael Aaron Safyan 2010-04-27 04:14:42

Do you mean * f(x) is O(g(x)), and * g(x) is Big-Omega(f(x)) ?Still I can't find a way to work if f(n) to determine n0 and c1 or c2

PLS 2010-04-27 04:22:37

@PLS, no I mean that f is big-oh g and g is big-oh f. You don't need to find specific values of n0 or N0... this is simply a formality that allows you to consider only the dominating terms. You also don't need to find specific values for c1 and c2, you just need to show that the highest-order term for both has the same form (so that you could easily choose a c1 or c2 to make it how you want).

Michael Aaron Safyan 2010-04-27 04:34:02

HINT: if you take (n^2+1)^10, the leading order term will be n^20.

Michael Aaron Safyan 2010-04-27 04:35:59

I know that, thanks for helping.My problem is how to manipulate this concepts to prove my assertion.

PLS 2010-04-27 04:39:53

HINT: (n^2+1)^10 = n^20 + k n^18 + ... Find out the value of k, and then compute the value of n=n0 such that kn^18 = n^20 ... For all values of n greater than n0, you know that (n^2+1)^10 < 2n^20 (because the first order term is n^20, and the second order term < n^20).

Michael Aaron Safyan 2010-04-27 05:06:10

I'm not really an expert at this, but couldn't you prove that f(n) E Ο(n) and that f(n) E Ω(n) and then argue that f(n) E Θ(n) due to the definition of intersection?

Liars_Paradox 2010-08-13 21:40:28

ansaurus

tags:

views:

answers:

Proving that a function f(n) belongs to a Big-Theta(g(n))

related questions