Common Algorithms and Their Complexity

Sorting:

• Quicksort – O(n logn), O(n^2) worst case
• Merge sort – O(n logn)
• Heap sort – O(n logn)
• Bubble sort – O(n^2)
• Insertion sort – O(n^2)
• Selection sort – O(n^2)

Graphs:

• Depth-first search – O(E + V), E = edges, V = vertices
• Breadth-first Search – O(E + V), E = edges, V = vertices
• Shortest-path (using Min-heap) – O(E + V) log v

Searching:

• Unsorted array – O(n)
• Sorted array with binary search – O(log n)
• Binary search tree – O(log n)
• Hash table – O(1)

Special Case:

• Traveling salesman – O(n!)

Often, O(n!) is really just shorthand for “brute force, try every single possibility!”.

Feature Comments

They create solutions in n^3 or worse for simple tasks.
understanding big-o means you had to have some education in computer science. Most programmers I have met have never heard of it.
True, most programmers don’t even know what is it and are missing out on its value at the analysis phase.
the ‘order’ or an algorithm is like n, or log(n), or n^2, or n^3. You want it to be a low order, n^2 or n^3 is a ‘bad’ algorithm

–EOF (The Ultimate Computing & Technology Blog) —