1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Big-Oh Problem

  1. Sep 3, 2005 #1
    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.
  2. jcsd
  3. Sep 3, 2005 #2
    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: Sep 3, 2005
  4. Sep 3, 2005 #3


    User Avatar
    Homework Helper

    What are you talking about?
    That is not a composite function.
    Last edited: Sep 3, 2005
  5. Sep 3, 2005 #4
    Sorry :redface: had no idea this was of asymptopic notation!
    well, I thought it was just a normal composite function, like those in early algebra :frown:

    Then again, it would have been
    K-12 forum in that case :blushing:
    Last edited: Sep 3, 2005
  6. Sep 4, 2005 #5


    User Avatar
    Homework Helper

    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
    if s(x) is strictly increasing when x>0
    s(x+y)>s(x) whenever x,y>0
    x^2 and log2(x) meet this requirement and each allow further simplification
    (f(n))^2 is O((g(n))^2)
    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) 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
  7. Sep 4, 2005 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  8. Sep 4, 2005 #7
    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.
  9. Sep 4, 2005 #8


    User Avatar
    Gold Member

    Drat. Sucked in by a thread title again.

    Should have wised up when I noticed that the topic section wasn't Biology...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook