Understanding Big-Oh Problems with Two Parts

[IcyBlueRose]

I'm having a problem with a Big-Oh problem, and I think it's more that I'm not understanding what the problem is asking and that I'm not completely understanding the definitions. There are two parts of the problem:

Here is the problem verbatim:
********************************************************
Assume you have functions f and g such that f(n) is O(g(n)). For each of the following statements, decide whether you think it is true or false and give a proof or counterexample.

A. log2 f(n) is O(log2 g(n)).
B. f(n)^2 is O(g(n)^2 ).

*********************************************************
(In part a the 2 is a subscript)

Does anyone have any pointers? The book I'm using doesn't give an example like it, so I'm not even really sure what it's asking.

 

[bomba923]

Assuming $$O [ g ( n ) ]$$ is a composite function, let:
$$g\left( n \right) = 5n$$
$$O\left( n \right) = 4n$$

And so,
$$\therefore f\left( n \right) = O\left[ {g\left( n \right)} \right] \Rightarrow f\left( n \right) = 20n$$

*However, for Part A:
$$\log _2 20n \ne 4\log _2 \left( {5n} \right) , n \ne \frac{{2^{\frac{2} {3}} }}{5}$$

*And for Part B:
$$400n^2 \ne 4\left( {25n^2 } \right) , n \ne 0$$

 

[lurflurf]

A counterexample?
Assuming $$O [ g ( n ) ]$$ is a composite function, let:
$$g\left( n \right) = 5n$$
$$O\left( n \right) = 4n$$

And so,
$$\therefore f\left( n \right) = O\left[ {g\left( n \right)} \right] = f\left( n \right) = 20n$$

*However, for Part A:
$$\log _2 20n \ne 4\log _2 \left( {5n} \right)$$

*And for Part B:
$$400n^2 \ne 4\left( {25n^2 } \right) , n \ne 0$$

Both (a) & (b) are false, I believe.

What are you talking about?
That is not a composite function.
http://mathworld.wolfram.com/AsymptoticNotation.html

 

[bomba923]

What are you taliking about?
http://mathworld.wolfram.com/AsymptoticNotation.html

Assuming $$O [ g ( n ) ]$$ is a composite function,

Sorry had no idea this was of asymptopic notation!
well, I thought it was just a normal composite function, like those in early algebra

Then again, it would have been
K-12 forum in that case
Sorry--sorry

 

[lurflurf]

So
f(n) is O(g(n)) means
|f(n)|<A*g(n) for some constant A
You should state if this is for all n, or in the limit.
Also is f>0
I will assume f>0 so that
0<f(n)<A*g(n)
if s(x) is strictly increasing when x>0
ie
s(x+y)>s(x) whenever x,y>0
then
f(n)<A*g(n)
implies
s(f(n))<s(A*g(n))
x^2 and log2(x) meet this requirement and each allow further simplification
f(n)<A*g(n)
so
(f(n))^2<(A*g(n))^2
(f(n))^2<(A^2)*(g(n))^2
is
(f(n))^2 is O((g(n))^2)
true?
f(n)<A*g(n)
log2(f(n))<log2(A*g(n))
log2(f(n))<log2(A)+log2(g(n))
This puts much doubt on
log2 f(n) is O(log2 g(n))
consider f(n)=2^(-n^2) g(n)=2^(-n)
f(n)<2*g(n)
so
f(n) is O(g(n))
log2 f=-n^2 log2 g=-n
so we have g<0 hance falsehood, but even if
log2 f(n) is O(|log2 g(n)|) were intended
n^2 is O(n) is also false

 

[Hurkyl]

The book I'm using doesn't give an example like it, so I'm not even really sure what it's asking.

There are examples in your calculus book. :tongue2: (At least if you've learned the theorem that characterizes asymptotic notation in terms of limits)

But honestly, these are straightforward with the algebraic definition as well.

 

[IcyBlueRose]

Thanks for the pointers.

No, there aren't examples in my calc book I've taken calc I, II and III, but this is for my Algorithms computer science class.

 

[DaveC426913]

Drat. Sucked in by a thread title again.

Should have wised up when I noticed that the topic section wasn't Biology...