Proving that a function f(n) belongs to a Big-Theta(g(n))
Posted
by PLS
on Stack Overflow
See other posts from Stack Overflow
or by PLS
Published on 2010-04-27T04:05:49Z
Indexed on
2010/04/27
4:13 UTC
Read the original article
Hit count: 459
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
© Stack Overflow or respective owner