I know that bubble sort has average time complexity O(n^2). Can anyone explain how to calculate this complexity? I usually find just people saying this is the average complexity but I don't know why. (In other words what is the average complexity for random permutation of numbers from 1 to n)
Asked
Active
Viewed 1,826 times
1
-
@AndrewMorton I guess I cannot understand how do I know that these calculations for the worst case (= I must swap every element) are calculations for average case? In other words, how to represent random permutation of n numbers in this calculation? – Superian007 Mar 14 '15 at 16:14
-
@Superian007: As a starting point Knuth's The Art Of Computer Programming treats bubblesort in section 5.2.2, eq(11) therein gives O(n²) exchanges needed in the average case. (Yes, I know, outside references are not appropriate for SO, but I'd have to reread 5.1 and 5.2 to summarize the argument.) – Ulrich Schwarz Mar 14 '15 at 20:59
1 Answers
-2
If the complexity is O(n^2), that would suggest that an algorithm must perform some operation on every combination of two elements of the input.
First of all, note that Bubble Sort compares adjacent items and swaps them over if they are out of order.
In the best case Bubble Sort is O(n). This is when the list is already sorted. It can pass over the list once and only needs to compare each item once with its neighbour before establishing that it is already sorted.
O(n^2) is the worst case for Bubble Sort. This is when the input list is already reverse sorted. Think about how the algorithm moves the first item from index 0 to it's sorted position at index n-1. It will have to compare that item to every other item once (n operations). It repeats this process with every item, hence O(n^2).
Peter Hall
- 53,120
- 14
- 139
- 204
-
2But how to calculate the average complexity? How do I know it will be same as worst complexity? – Superian007 Mar 14 '15 at 15:58