Algorithm Running Time

From: Gary Nastrasio (noemail_at_please.com)
Date: 01/17/04 

Date: Sat, 17 Jan 2004 16:48:53 GMT

Hello everyone. I'm currently in a 3rd year algorithm class where we
discuss running times. I have a fair grasp of the concepts, but some
things are confusing and my text book, Introduction To Algorithms
(Cormen et al.) isn't very clear on some topics. For example, I'm
having a bit of trouble with 2 questions in particular (@ is big-theta):

1) If f(n) is @(g(n)), then 2^f(n) is @(2^g(n)).

I say false and justify it as follows:
Take f(n) = 3n^2 + 2n, g(n) = n^2.

c1 * g(n) <= f(n) <= c2 * g(n)

Divide through by g(n) and you are left with:

c1 <= 2^(2n^2 + 2n) <= c2.

Clearly c2 cannot exist since the limit as n approaches infinity is
infinity, therefore this statement is false.

Is this a valid argument? 

----
2) f(n) is @(g(n)), then lg f(n) is @(lg gn(n))
I say this is true, because in the same situation as above whenever I 
divide through by g(n), I'm left with c1 <= lg x / lg y <= 2, which when 
you take the limit as n approaches infinity, it equals 0.  Therefore c1 
and c2 can exist.  How can I structure a formal proof of this, if indeed 
my hypothesis is correct?
Are there any texts or websites that discuss these types of questions 
further?
Thanks for any help,
Gary