I have these questions from a book:

show that if f(n)=theta(log2 n) then f(n)=theta (log10 n)

show that if f(n)=o(g(n)) and g(n)=o(f(n)) then f(n)=theta(g(n))

how to prove? can anyone help me with it?

Printable View

- September 29th 2011, 02:03 AMEvangelineSmall-o and Theta questions
I have these questions from a book:

show that if f(n)=theta(log2 n) then f(n)=theta (log10 n)

show that if f(n)=o(g(n)) and g(n)=o(f(n)) then f(n)=theta(g(n))

how to prove? can anyone help me with it? - September 29th 2011, 02:06 AMSironRe: please help me with these quetions
The first proposition, do you mean:

? - September 29th 2011, 01:09 PMemakarovRe: please help me with these quetions
To show the first statement, write the definition of and note that .

The second statement is a little odd because I believe that if f(n) = o(g(n)) and g(n) = o(f(n)), then f and g must be 0 from some point. However, the fact that g(n) = o(f(n)) implies that g(n) = O(f(n)), and this is almost the same as (up to absolute value). - September 29th 2011, 01:17 PMEvangelineRe: Small-o and Theta questionsQuote:

Quote:

To show the first statement, write the definition of http://latex.codecogs.com/png.latex?%5CTheta and note that http://latex.codecogs.com/png.latex?...Clog_%7B10%7Dn.

The second statement is a little odd because I believe that if f(n) = o(g(n)) and g(n) = o(f(n)), then f and g must be 0 from some point. However, the fact that g(n) = o(f(n)) implies that g(n) = O(f(n)), and this is almost the same as http://latex.codecogs.com/png.latex?...%28g%28n%29%29 (up to absolute value).