**Big-O:**- Describes how the algorithm scales and performs, in terms of either the execution time required or the space used.
- Is relative representation of complexity. This allows you to reduce an algorithm to a variable which in turn allows you to easily compare it to another.
- Describes an upper limit on the growth of a function, in the other words the "worst case scenario".

*There is also Big-Omega notation which looks at the*

*lower bound / "best case scenario" stating that the algorithm will take at least X amount of time and Big-Theta which is*

*tight bound to both lower and upper / "average".*

**Some quick observations in determining Big-O:**

- A Sequence of statements, or things like conditional checks are constant: O(1)
- A loop of statements result in : O(n) n being the number of loop executions.
- Nested loops are multiplied together: O(n
^{2}) where n is the times the outer loop executes and m is the times the inner loop executes.

**Comparing the common notation examples:**

*(Thanks to Algorithms: Big-Oh Notation.)*

n | Constant O(1) | O(log n) | Linear O(n) | Linear Logarithmic O(n log n) | Quadractic O(n ^{2}) | Cubic 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 |

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

1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 10^{12} | 10^{16} |

**Java code example:**

Show examples of notations in the table above.

**Common Data Structures and Relative functions:****Lists and Sets:**

Structure | get | add | remove | contains |
---|---|---|---|---|

ArrayList | O(1) | O(1)* | O(n) | O(n) |

LinkedList | O(n) | O(1) | O(1) | O(n) |

HashSet | O(1) | O(1) | O(1) | O(1) |

LinkedHashSet | O(1) | O(1) | O(1) | O(1) |

TreeSet | O(log n) | O(log n) | O(log n) | O(log n) |

** ArrayList Notes:**
Thanks to reader comments, the add method on an ArrayList should be:
O(1) amortized (and O(n) in worse case).
Useful reference links:*

**Maps:**

Structure | get | put | remove | containsKey |
---|---|---|---|---|

HashMap | O(1) | O(1) | O(1) | O(1) |

LinkedHashMap | O(1) | O(1) | O(1) | O(1) |

TreeMap | O(log n) | O(log n) | O(log n) | O(log n) |

**References:**

Algorithmic Complexity and Big-O Notation.