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

    lurflurf

    User Avatar
    Homework Helper

    What are you talking about?
    That is not a composite function.
    http://mathworld.wolfram.com/AsymptoticNotation.html
     
    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:
    Sorry--sorry
     
    Last edited: Sep 3, 2005
  6. Sep 4, 2005 #5

    lurflurf

    User Avatar
    Homework Helper

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

    Hurkyl

    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

    DaveC426913

    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