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 .
6
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.
1
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).
From Introduction to Algorithms By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein:
In general, we discuss the average-case running time when
the probability distribution is over the inputs to the algorithm, and we discuss the expected running time when the algorithm itself makes random choices.