average case complexity

i have a question about average case complexity, if you have a for loop

 
for (int i = 0; i < n; i++) // would this still be O(n) 
that loop itself is O(n), yes. There are no 'cases' for this loop: it will loop N times no matter what, until you provide additional code that might modify this behavior.

For example the loop body could set i = n+1 which would change it to a O(1) problem.

average case can only exist if you have best and worst cases, which require an algorithm that varies in complexity based off the data. for example shell short is N^(c+1)/c on the worst case but only does O(N) for an already sorted list (all it does is iterate and validate that it is already sorted).

Last edited on
Er, not quite.

That loop is ϴ(n) [unless the body does something to it as jonnin commented]: its worst case O(n) and best case Ω(n) are the same. Further, its average case complexity is also ϴ(n)... because all loops have the same complexity. This follows from the definition of the average.


Keep in mind that average case is highly dependent on how likely each input is. If the worst case inputs are unlikely but the not-worst-case inputs are very common, or vice versa, then average case complexity tells you something very useful about the algorithm.

As the probability of having a good or bad input approaches 50%, average case provides you with less useful information.

In other words, for average case to be useful, you also have to know what inputs are most common.

For example: using an insertion sort to fix a single out-of-order item in an otherwise already-sorted array is about as efficient as you can get. So if you only occasionally add a single element to an array, insertion sort is the way to go — on average, you only invoke one of the best case behaviors.

But if you are dealing with randomized data, insertion sort quickly hits its worst case behavior, and your average case is not good; use an introsort or mergesort instead.

Hope this helps.
Tangentially, and mostly just because I like to repeat it when order notation comes up (hence my name), let us always bear in mind that complexity doesn't tell you how fast it is; just how it will scale. If performance is being chased, algorithmic complexity is one input amongst many.
Topic archived. No new replies allowed.