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

Average case vs. expectation

  1. Aug 16, 2009 #1

    I am not sure if I understand well : is there a difference between avarage case complexity to expectation of running time?

    thank you

  2. jcsd
  3. Aug 17, 2009 #2
    Well, different authors might use them in different ways, but here's how I learned it...
    "Average case" running time is for a deterministic algorithm (the most familiar example that you use average case runtime for is quicksort). It is the expected value of the running time that the algorithm would have if inputs were chosen randomly.

    "Expected" running time is usually for a randomized algorithm (for example, Karger's algorithm). It is the expected value for the runtime of the algorithm on a particular input. You might also speak of expected worst case running time, which would be the worst case of the expected running time over all inputs of a certain size.
  4. Aug 19, 2009 #3
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook