# Big O Notation

May 18, 2024
note-to-self

Used to analyze worst-case (usually) complexity to check resource requirements for runtime as inputs increase. Not about the hardware, etc. High level view. How long: time complexity. Memory consumption: space complexity.

Common examples (time complexity):

- O(1): Constant. Input size won't anG major effect. (bookmark example, array key)
- O(n): Linear. The runtime grows linearly with the input size. (reading the book example, interating over array)
- O(n^2): Quadratic. Common in algorithms with nested loops. (many array sorting functions)
- O(log n): Logarithmic. Common in algorithms like binary search. (dictionary example)
- O(n log n): Linearithmic. Seen in efficient sorting algorithms like merge sort and quicksort.
- O(2^n): Exponential. Often seen in brute-force algorithms.
- O(n!): Factorial. Extremely inefficient and usually impractical for large inputs.

Examples: