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
    Hi,

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

    thank you

    Naftali
     
  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
    Thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Average case vs. expectation
  1. Another Word for Case (Replies: 4)

Loading...