Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complexity Big O, little o

  1. Sep 9, 2012 #1

    When we have f(n) [itex]\in[/itex] o(g(n)) and g(n) [itex]\in[/itex] O(H(n))

    Can I proove that h(n)-f(n) [itex]\in[/itex] o(g(n))?

    Obviously I don't want you to give me the answer, but some hints and maybe which definitions of O and o I should use.

  2. jcsd
  3. Sep 9, 2012 #2
    Ok, I believe I came up with a counter example:

    If f(n)=n, g(n)=[itex]n^{2}[/itex] and h(n)=[itex]n^{3}[/itex]

    When I looked for the limit of the difference / g(n) it cannot give 0.

    Could you please confirm this result?

  4. Sep 9, 2012 #3
    What definitions are you talking about? Also how does H(n) relate to h(n). Forgive me for asking but I just don't know what you are referring to.
  5. Sep 9, 2012 #4
    Thank you ramsey, it was the same function h and the definitions I'm talking about are of big O of a function and small o.

    For example Big O of g(n) is the set of function f(n), f(n)≤c g(n). (not complete definition)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook