I wish I had this table back in 1984 when I was trying to understand this stuff.

Big O Notation | Name | Example(s) |
---|---|---|

O(1) |
Constant | # Odd or Even number, # Look-up table (on average) |

O(log n) |
Logarithmic | # Finding element on sorted array with binary search |

O(n) |
Linear | # Find max element in unsorted array, # Duplicate elements in array with Hash Map |

O(n log n) |
Linearithmic | # Sorting elements in array with merge sort |

O(n^{2}) |
Quadratic | # Duplicate elements in array (naïve),# Sorting array with bubble sort |

O(n^{3}) |
Cubic | # 3 variables equation solver |

O(2^{n}) |
Exponential | # Find all subsets |

O(n!) |
Factorial | # Find all permutations of a given set/string |

and I now can firmly feel the difference between polynomial and exponential well worth this example:

n = 10 | 100 | 1000

```
```n^2 = 100 | 10000 | 1000000

`k^n = k^10 | k^100 | k^1000`

## 0 Comments

Add Yours →