Big-O and functions?

Question

Consider functions f(n) and g(n) whose values are non-negative.

1. Show that if f(n) is O(n^a) and g(n) is O(n^b), then f(n)g(n) is O(n^(a+b)).

2. Show that if f(n) is Θ(n^a) and g(n) is Θ(n^b), then f(n)g(n) is Θ(n^(a+b)).

Is this just really simple algebra and multiplication or does the Big-O come into play? Because i know n^a * n^b is n^(a+b)

Answer 1

1.  You are correct.  f(n) = O(n^a) iff for some constant k we have f(n) < kn^a, and similarly, g(n) < jn^b for some constant j.  Then f(n)g(n) <

(jk)(n^a)*(n^b) = (jk)n^(a+b), so f(n)g(n) = O(n^(a+b)).

2.  I don't know what theta(n^a) means.  But if f(n) = theta(n^a) means lim(n-->inf){f(n)/n^a) = 0, then the proof of 2. is that the limit of a product is the product of the limits (if both exist).