Page 1 of 1

complexity problem

Posted: Wed Dec 28, 2005 10:49 pm
by midra
I need help to prove a problem about complexity.
Let a Function defined by:
F(0) = 3
F(n+1) = 3 * F(n) + h(n), where h ∈ θ(n)
Prove that F ∈ O(3^n)

I get that the function is O(n*3^n), but I don't know if I did it wrong or how to do it

Please ask me if the problem is not clear enough.
thanks for reading

Posted: Thu Dec 29, 2005 9:24 am
by StepLg
what is θ(n)? - possible it means infinitesimal function when n tend to infinity? Then our function F(n) = 3*F(n-1)+h(n) = 3*(3*F(n-2)+h(n-1)) = ... = 3^n+h(n)+3*h(n-1)+...+h(0). And if h(n) is a infinitesimal function then product and sum of terminal number of them is a infinitesimal function too. And it means that F(n) <= 3^n + Const, because an infinitesimal function is bounded.
Definition O(f(x))=g(x) : |g(x)/f(x)| <=C or |g(x)| = C*|f(x)| where C is a constant. Then F(n) = O(3^n)

Posted: Thu Dec 29, 2005 3:47 pm
by cansado
I have the same problem... the definition i have for θ(n) (or average complexity order) is:

f = θ(g) or f ∈ θ(g) if f grows (eventually) at the same rate as g, and:
θ(g) = {f | ∃N, K1, K2 > 0, such that, if n >= N then K1*g(n) <= f(n) <= K2*g(n)}