Big O Notation - Falmouth-Games-Academy/comp350-research-journal GitHub Wiki
Generally, the efficiency of an algorithm can be gauged by how long it takes to run as a function of the size of the input [1]. This can be used as a measure when optimising. Big O Notation (The capital O also known as Landau's Symbol) sometimes called asymptotic analysis is used to describe the Time Complexity for a program. Both Time Complexity and Space Complexity are functions of the size of the problem to be solved [2]. W. Kuo and M. J. Zuo [2] believe that while Space Complexity is of concern, it is often not as important as the Time Complexity. Big O notation ranks the efficiency of an algorithm, it does this with regard to "O" and "n" examples below. O refers to the order of the function and its growth rate and n is the length of the array to be sorted [3].
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Find if binary number is odd or even |
| O(log(n)) | Logarithmic | Find item in sorted array using binary search |
| O(log(log(n)) | Double logarithmic (iterative logarithmic) | |
| o(n) | Sublinear | |
| O(n) | Linear | Find item in unsorted array |
| O(n log(n)) | Loglinear, Linearithmic, Quasilinear, or Supralinear | Merge sort / heap sort |
| O(n^2) | Quadratic | Bubble sort / insertion sort |
| O(n^3) | Cubic | |
| O(n^c) | Polynomial (different class for each c > 1) | |
| O(c^n) | Exponential (different class for each c > 1) | Travelling salesman problem using dynamic programming |
| O(n!) | Factorial | Travelling salesman problem via brute force |
[1] Danziger, P. "Big O Notation." Journal, Retrieve: April (2010).
[2] W. Kuo and M. J. Zuo, Optimal reliability modeling: principles and applications. John Wiley & Sons, 2003 , p. 62.
[4] http://bigocheatsheet.com/
[5] Brilliant - Choosing a Sorting Algorithm, accessed on 9th Febuary 2019.