Big-O Notation

Download:Big O Notation

Speed of an Algorithm:

Big-O Notation is used to express the time complexity, or performance of an algorithm.

Some algorithms are slower than others. The speed of an algorithm is usually expressed as a function of ‘n’.

N = the number of items that have to be processed.

There are three types of speed varies in algorithm:

  • Best Case Scenario. (If you were searching for an item in a list and the first term was your search term)
  • Average Time.
  • Worst Case Scenario (If the search term was the very last term in the list)

The Big-O represents the increase in processing time as the size of n increases. It is a rating system for the complexity of an algorithm. The higher the ‘Big-O’, the slower the algorithm.

Best to Worst Times:

  1. O(1) – Constant Time. O(1) describes an algorithm that takes constant time (the same amount of time) to execute regardless of the size of the input data set. This is the fastest and least complex.
  2. O(log n) – Logarithmic Time. This will grow very slowly as the size of the data set increases.
  3. O(n) – Linear Time. This describes an algorithm whose performance will grow in linear time, in direct proportion to the size of the data set.
  4. O(n^2) – Polynomial Time. This describes an algorithm whose performance is directly proportional to the square of the size of the data set. A program with two nested loops each performed n times will typically have an order of time complexity O(n^2). The running time of the algorithm grows in polynomial time.
  5. O(X^n) – Exponential Time. The number of operations shoots up very high as n increases. This is the slowest and most complex.

 622 total views,  1 views today