complexity problem
Posted: Wed Dec 28, 2005 10:49 pm
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
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