Famous Algorithms and their Running Times

I recently did some searching and had a very hard time finding a simple yet comprehensive listing of the running times for various sorting algorithms. This surprised me, so I decided to make the Internet a little better by writing this post.

This is an ongoing post, and will be updated with more algorithms as time goes on. It is not limited to just array sorting; it could be a graph search problem, a regression, or any other algorithm as long as it's pretty well-known. I welcome your additions in the comments section.

Algorithm Worst-Case Average-Case Best-Case Space Growth
Selection Sort O(n2) O(n2) O(n2) O(1)
Insertion Sort O(n2) O(n2) O(n) O(1)
Bubble Sort O(n2) O(n2) O(n) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Heapsort O(n log n) O(n log n) O(n log n) O(1)
Quicksort O(n2) O(n log n) O(n log n) O(n)
Tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *