Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Common Big-O Complexities

Big O notation categorizes algorithms based on their growth rates. Here are the most common types, ordered from fastest (most efficient) to slowest (least efficient):

  1. O(1) - Constant Time

    • Execution time doesn’t depend on input size.
    • Example: Accessing an array element by index.
    • Graph: Flat line (no growth).

  2. O(log n) - Logarithmic Time

    • Time grows logarithmically with input size.
    • Example: Binary search.
    • Graph: Very slow growth, flattens out.

  3. O(n) - Linear Time

    • Time grows linearly with input size.
    • Example: Linear search through an array.
    • Graph: Straight line.

  4. O(n log n) - Linearithmic Time

    • Time grows as ( n ) times the logarithm of ( n ).
    • Example: Efficient sorting algorithms like Merge Sort or Quick Sort.
    • Graph: Slightly steeper than linear.

  5. O(n²) - Quadratic Time

    • Time grows quadratically with input size.
    • Example: Nested loops, like in Bubble Sort.
    • Graph: Parabolic curve.

  6. O(n³) - Cubic Time

    • Time grows cubically with input size.
    • Example: Matrix multiplication with three nested loops.
    • Graph: Steep parabolic curve.

  7. O(2ⁿ) - Exponential Time

    • Time doubles with each additional input.
    • Example: Solving the traveling salesman problem via brute force.
    • Graph: Extremely steep, quickly becomes impractical.

  8. O(n!) - Factorial Time

    • Time grows factorially, extremely inefficient for large ( n ).
    • Example: Generating all permutations of a set.
    • Graph: Explosive growth, worst-case scenario.

📊 Frequently Used Big-O Complexities

NotationNameExample Algorithm
O(1)ConstantAccessing an array element
O(log n)LogarithmicBinary search
O(n)LinearIterating through a list
O(n log n)Log-linearMerge sort, Quick sort (average)
O(n²)QuadraticBubble sort
O(2ⁿ)ExponentialRecursive Fibonacci

🔍 Related Notations

While Big-O describes the upper bound of growth rate:

  • Big Theta (Θ) → Tight bound (exact growth rate).
  • Big Omega (Ω) → Lower bound (best-case or minimum growth).

These are less commonly used in casual discussions but provide more precise performance characterizations.

💡 Practical Use

  • Algorithm Selection: Big-O helps developers pick algorithms that scale well with large datasets.
  • Space Complexity: Big-O also applies to memory usage, not just time.
  • Focus on Trends: Ignore constants and small terms — large input size behavior is what matters most.

▶ Next: What is Complexity?