• Support PF! Buy your school textbooks, materials and every day products Here!

Big-Oh Problem

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.
 

Answers and Replies

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

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

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

*And for Part B:
[tex] 400n^2 \ne 4\left( {25n^2 } \right) , n \ne 0 [/tex]
 
Last edited:
lurflurf
Homework Helper
2,419
122
bomba923 said:
A counterexample?
Assuming [tex] O [ g ( n ) ] [/tex] is a composite function, let:
[tex] g\left( n \right) = 5n [/tex]
[tex] O\left( n \right) = 4n [/tex]

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

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

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

Both (a) & (b) are false, I believe.
What are you talking about?
That is not a composite function.
http://mathworld.wolfram.com/AsymptoticNotation.html
 
Last edited:
732
0
Last edited:
lurflurf
Homework Helper
2,419
122
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
Staff Emeritus
Science Advisor
Gold Member
14,843
17
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.
 
Thanks for the pointers.

No, there aren't examples in my calc book :smile: I've taken calc I, II and III, but this is for my Algorithms computer science class.
 
DaveC426913
Gold Member
18,332
1,940
Drat. Sucked in by a thread title again.

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

Related Threads for: Big-Oh Problem

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
4
Views
1K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
1
Views
4K
Replies
1
Views
3K
Replies
1
Views
2K
Top