Best Algorithms based on Order of Complexity

Share this: Google+
< Contents | Previous | Next >

In the last section, we have learned about the time estimation based on algorithm complexity. The algorithm complexity is measured through asymptotic functions. In this section, we will mention the order of the best, good and bad algorithm time complexity.

Knowing the order of algorithm complexity is important because through it we can analyze, evaluate and design better algorithms.

Rank 1: Constant Time Complexity

We should say that the best algorithm would have time complexity of O(1) which is a constant. This means the run time of the algorithm is either independent of the data size or there is a constant such that the runtime is bounded above by a constant. Nothing is faster than O(1) because O(1/n) is basically the same as O(1) based on the definition bounded above by a constant. The examples of algorithm (including the baby step) with fixed time complexity are the following:

Assignment to a variable
Procedure entry
Procedure exit
Return value from a function (return x;)
Accessing Array Index (float x = Arr[1000];)
Determining if a number is even or odd
Swap values between two variables
Accessing a HashMap value
Inserting a node in Linked List
Pushing and Popping on Stack
Insertion and Removal from Queue
Finding out the parent or left/right child of a node in a tree stored in Array
Jumping to Next/Previous element or deleting an element in Doubly Linked List

Rank 2: Double Logarithmic

Based on the limited list of asymptotic functions in the previous section, the second best running time complexity in our list of asymptotic functions is O(log(log(n))) which is double-logarithmic. The examples of algorithms with double-logarithm time complexity are:

Cheriton-Tarjan MST algorithm
X-fast trie algorithm, Y-fast trie algorithm: a data structure for storing integers from a bounded domain
Tango tree algorithm
Van Emde Boas tree
multisplay tree data structure
Hopcroft-Fortune closest pair of points algorithm
Interpolation search (average)

Rank 3: Logarithmic

Next, third best running time complexity is O(log(n)) which is logarithmic. The examples of algorithms with logarithm time complexity are:

Binary Search
Search, Insert, delete in in a binary search tree (BST)
Calculating Fibonacci Numbers
Primality test Fermat method
Manually looking up people’s name in a phone book

Rank 4: Square Root

Still, the next best running time complexity is ( which is square root. The examples of algorithms with square root time complexity are:

Grover's algorithm for searching an unsorted database
point updates and range sum queries
Baby-step giant-step algorithm
Orthogonal range queries on a bidimensional k-d tree
Range Min/Max Querying (RMQ)
Primality test
Prime factorization

Rank 5: Linear

The next best algorithms would be of linear running time O(n). This means the performance of the algorithm is linearly in direct proportion to the input data size. We know that a linear time complexity means a single for-next loop. The examples of algorithms with linear complexity are:

Traversing an array in one For-Next loop
Traversing a linked list
Boyer–Moore–Horspool algorithm
Linear Search
Deletion of a specific element in a Linked List (Not sorted)
Comparing two strings
Checking for Palindrome
Counting/Bucket Sort

Rank 6: Log-Linear

The next best running time is O(n log(n)) or log-linear. Usually Divide and Conquer type of algorithms which are the optimization from O(n^2) algorithms may produce this running time. The examples of algorithms with log-linear complexity are:

Note: There are boundary (or intersection between two asymptotic functions) in which we say that one asymptotic function is faster than the other. For example: Schönhage–Strassen algorithm to multiply large integers has complexity of O(n log(n) log(log(n)) which is a little bit faster than O(n log(n)) if n < 10 billion but slower than O(n log(n)) if n>10 billion. If your data size is less than the boundary, you may select the appropriate algorithm.

Rank 7: Quadratic

Quadratic running time O(n^2) is the next good algorithm. We know that quadratic complexity means Traversing a simple 2D array using double For-Next loop. The examples of algorithms with quadratic complexity are:

Rank 8: Cubic

Cubic running time or other higher order polynomial asymptotic function is generally still trackable and should be considered as good algorithm if there is no better alternative and the data size is limited. The examples of algorithms with quadratic complexity are:

Floyd–Warshall algorithm

Rank 9: Exponential

In general, algorithm with exponential time complexity O(c^n) are considered bad algorithm in term of running time. The examples of algorithms with exponential complexity are:

recursive calculation of Fibonacci numbers

Rank 10: Factorial

The worst algorithm in term of time complexity would be factorial O(n!). The examples of algorithms with exponential complexity are:

List all permutations in an array (of course)
Brute Force or naïve solution of Traveling Salesman Problem

Summary

In summary, if we put n = 1 million as our standard of comparison, the best algorithms should have computational speed faster than or equal to O(n log(n)), such as O(log n), O(log log n), O(sqrt(n)), O(n) or O(n log(n)). Look at the table above. You can see that for n=1 million, the O(n log(n)) takes only seconds to finish.

< Contents | Previous | Next >