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:

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) —

GD Star Rating
loading...
324 words
Last Post: Linux Fun Commands: Banner and Toilet
Next Post: How to Invoke APIs - The Javascript/Ajax/JQuery Example

The Permanent URL is: Common Algorithms and Their Complexity

Leave a Reply