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
complexity problem
Moderator: Board moderators
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)
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)