Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Let's say we want to analyze running time of algorithms. Sometimes we say that we want to find the running time of an algorithm when the input size is n and for the worst possible case it is denote it by O(n). Sometimes though I see books/papers saying that we need to find the expected time of an algorithm. Also sometimes the average running time is used .

What is "expected time"? In which cases is it useful to find expected time instead of worst case time?

Edit: I think there is a subtle difference between expected running time and average running time but I am not sure . Through this post I want to know the exact difference if any .

share|improve this question
1  
Presumably they mean the average case.. –  Martijn Pieters Aug 4 '12 at 16:30
3  
The expected value of a probability distribution function is described as the integral of x*f(x) from negative to positive infinity. The expected time would be derived by determining the probability distribution of all possible times and then taking the expected value. This operation is more commonly known as calculating the mean or calculating the average. –  Joel Cornett Aug 4 '12 at 16:31
1  
@JoelCornett: That would make a fine answer if you posted it.. –  Martijn Pieters Aug 4 '12 at 16:34
    
@MartijnPieters: No, the average case makes an assumption about the probability distribution of the inputs, the expected case doesn't. –  Jörg W Mittag Aug 4 '12 at 16:38
    
@JörgWMittag: Right, if you know the real-world probability distribution of your inputs, you can ignore the average case. In other words, the expected case is the time your algorithm takes give the probability distribution of expected input sets. –  Martijn Pieters Aug 4 '12 at 16:41
add comment

2 Answers

up vote 10 down vote accepted

Expected time is just the average, expected, running time of the algorithm using the intended input.

Say you've got some few million user records and want to sort them, you might want to use an algorithm which is the most suitable for your input, and as such gives the best expected running time, as opposed to an algorithm which has better worst-case running time but worse expected running time.

Sometimes for example the constant factors for the time-complexity of an algorithm are so high that it makes sense to use algorithms with worse time-complexity but smaller constant factors, as it gives you better expected running time with small input, even though it would get horribly outperformed with bigger input.

Perhaps a better example would be the classic quicksort algorithm, which has worst-case running time of O(n²) but expected average running time of O(n log n), regardless of input. This is because the algorithm uses(or rather, may use, depending on the implementation) randomization. So it's a so-called randomized algorithm. It runs a bit differently with every invocation even with the same input. As such, thre's no universal worst-case input for the implementation, because the worst-case input depends on the way the algorithm chooses the pivot for dividing the given input. And as such, one can't just supply some pre-defined input causing the worst-case running time. This is often the case with randomized algorithms, which aim for better expected, average running time regardless of the input.

It's all about using the right algorithm for the input at hand.

share|improve this answer
    
Excellent answer . Thanks . I think the difference between expected and average is that when we know the distribution of the inputs and run the algorithm it is called "average" and when we use a random number generator to permute the inputs at hand , it is called expected running time . Do you agree with this premise ? –  Geek Aug 8 '12 at 15:02
add comment

The expected running time of a randomized algorithm is a well-defined concept, just like the worst case running time. If an algorithm is randomized, its running time is also random, which means we can define the expected value of its running time.

A well-known example is Quicksort: if we pick the pivots at random, we can prove that its expected running time becomes O(n log n), even though its worst case running time remains O(n^2). An example where randomization is very powerful is the smallest enclosing circle problem: there is a simple algorithm whose worst case running time is O(n^3), but in expectation, its running time is only O(n).

Average running time is usually used when talking about the behavior of an algorithm 'for most inputs'. We define some way of randomly generating an input, for instance, we fill an array with random numbers, or we randomly permute the numbers 1 through n (so no duplicates), or we flip a coin and either get a descending or ascending set of numbers. The average running time of an algorithm for that random distribution of inputs is then the expected running time of the algorithm (in which case the algorithm may not be randomized, but the input is).

As an example: there are geometric problems for which algorithms exist that seem to work well at first sight, until you discover some very weird way of distributing, say, the input lines. If you assume the lines are randomly distributed, then it may be the case that these weird scenarios are extremely unlikely to occur, so your algorithm ends up being good.

Contrasting: expected running time is about how an algorithm performs 'unless you have bad luck' - retrying the same algorithm on the same input but with different random choices may lead to it being solved much faster. Average running time talks about how well an algorithm performs 'for most inputs' - trying the same algorithm again on the same input won't help you (except perhaps if the algorithm is also randomized).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.