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-O and big-omega question

  1. Jul 7, 2006 #1

    I am a bit confused here. Just say you're given code and it says to show the best-case analysis and the worst-case analysis. When you show the best-case, what should the answer be in? In big-O or big-omega? Similarly, if you show the worst-case, what should the answer be in? big-O or big-omega? Would it be correct to just show big-O for worst and best case? I am confused here about when to use both and how to use both when analysing best and worst case.
  2. jcsd
  3. Jul 7, 2006 #2


    User Avatar
    Science Advisor

    In each case, choose the option that tells you something about the runtime of the elements of some arbitrary sequence of inputs. Let these runtimes be given by the function A(n).

    Now let B(n) denote the runtimes of the elements of a similar sequence of worst-case inputs. You know that A(n) <= B(n). Now do you know anything additional about the long-term behavior of A(n) if you know
    a. [tex]B(n) \in O(f(n))[/tex]?
    b. [tex]B(n) \in \Omega(f(n))[/tex]?

    Choose the one that gives you more information about A(n). And take a similar argument for describing the best case inputs.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook