Terminology | Called As | Definition |
---|---|---|

O(1) | Constant Time | Time is taken for an operation, fixed number of steps |

E.g. Push and Pop operations for the stack. | ||

Enqueue and Deque operations for Queue. | ||

O(log n) | Logarithmic Time | Time was taken will double with each additional element in the input data set |

E.g. Binary Search | ||

Insert and Find operations in a Binary Search tree. | ||

Insert and Remove operations for a heap | ||

O(n) | Linear Time | A number of steps proportional to the size of the tasks. |

(If the size of the task increases the no of steps increases) | ||

E.g. Finding Max/Min element in a list. | ||

Sequential search in an unsorted list of n elements. | ||

Traversal of a tree with n nodes. | ||

Calculating iteratively n-factorial. | ||

Finding iteratively the nth Fibonacci number | ||

O(n log n) | Linean Arithmetic |
You are performing an O(log n) operation for each item in your input. Also called as Log-Linear, or QuasiLinear |

Most (efficient) sort algorithms are an example of this. | ||

O(n log n) . "n log n" time | ||

E.g. Quick Sort, Merge Sort | ||

O(n^{2}) |
Quadratic Time | The number of operations is proportional to the size of the task squared. |

E.g. Selection Sort of n elements. | ||

Comparing two-dimensional arrays of size n by n. | ||

Finding duplicates in an unsorted list of n elements | ||

(Implemented with two nested loops) | ||

2^{O(n)} |
Exponential Time | Which is common for artificial intelligence tasks and is really quite bad. Exponential-time algorithms begin to run the risk of having a decent-sized input not finish before the person wanting the result retires. |

O(n!) | Factorial time |

### Run time matrix for each Big O Term:

Input | Constant | Logarithmic | Linear | Linear Arithmatic | Quadratic | Cubic |

N | O(1) | O(log N) | O(N) | O(N log N) | O(N^{2}) |
O(N^{3}) |

1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | 1 | 1 | 2 | 2 | 4 | 8 |

4 | 1 | 2 | 4 | 8 | 16 | 64 |

8 | 1 | 3 | 8 | 24 | 64 | 512 |

16 | 1 | 4 | 16 | 64 | 256 | 4,096 |

1024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |