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.