ReviseAlgo Logo

Foundations

Big O Notation

Master Big O notation—the universal standard to classify algorithm efficiency, drop constants, and identify dominant growth terms.

Last Updated: July 31, 2026 • 15 min read

1. Introduction

What is Big O Notation?

Big O Notation is a mathematical syntax used in computer science to classify algorithms according to how their run time or space requirements grow as the input size (N) increases. The "O" stands for "Order of" (order of magnitude).

Why is it Important?

Big O allows software engineers to predict how code will behave at scale before shipping to production. It gives us a common vocabulary to discuss performance (e.g. "This approach is O(N log N) while the old one was O(N²)").

Where is it Used?

  • System Architecture: Selecting data structures during system design interviews (e.g. choosing between Hash Table O(1) lookup vs Array O(N) lookup).
  • Code Optimization: Identifying performance bottlenecks in web apps, mobile apps, and machine learning pipelines.

    • 2. Mental Model

    Imagine transferring a file from New York to London.

  • For small files (1 MB), Option A is much faster.
  • For huge files (10 TB), Option B is vastly superior!
    • Big O doesn't care about small inputs. It answers the question: "When N gets massive, which line grows faster?"

    3. Concept: The Three Rules of Big O

    To simplify complexity calculations, computer scientists follow three fundamental rules:

    Rule 1: Always Focus on Worst-Case Scenario

    Big O measures the upper bound. If searching an element in an unsorted list of N items:
  • Best Case: Item is at index 0 (1 step) → Ω(1) (Omega)
  • Worst Case: Item is at the very end or missing (N steps) → O(N) (Big O)

    • We always design systems assuming the worst-case scenario (O(N)).

    Rule 2: Drop Constants

    When calculating operations like 2N + 500:
  • As N reaches 1,000,000, the constant 500 is negligible.
  • The multiplier 2 changes speed slightly, but the rate of growth remains linear.
  • O(2N + 500) → O(N)

    • Rule 3: Keep Only the Dominant Term

    If an algorithm takes N² + 100N + 50 operations:
  • For N = 10,000:
    • - N² = 100,000,000 (99.9% of the total work!) - 100N = 1,000,000
  • The smaller terms (100N and 50) become insignificant.
  • O(N² + 100N + 50) → O(N²)

    • 4. Visuals

    The Big O Hierarchy (Best to Worst)

    Big O Complexity Reference Table

    NotationNameCommon ExamplePerformance Rating
    O(1)ConstantArray index access, HashMap lookup🟢 Excellent
    O(log N)LogarithmicBinary Search in sorted array🟢 Excellent
    O(N)LinearSingle loop over array🟡 Fair
    O(N log N)LinearithmicEfficient sorting (MergeSort, QuickSort)🟡 Fair
    O(N²)QuadraticNested loops (BubbleSort, brute force pair match)🔴 Poor
    O(2ⁿ)ExponentialRecursive Fibonacci without memoization🔴 Horrible
    O(N!)FactorialGenerating all permutations of a set🔴 Unusable for N > 12

    5. Real-World Examples

  • O(1) Hash Table Lookup: Redis key-value cache lookups take O(1) time, retrieving user sessions in microseconds regardless of millions of active users.
  • O(log N) Binary Search: Git bisect uses binary search over commit history to pinpoint which commit introduced a bug in 10 steps across 1,000 commits.
  • O(N log N) Database Indexing: PostgreSQL creates B-Tree indexes on tables using O(N log N) sorting so subsequent queries run in O(log N).

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    After writing code, the interviewer will ask: "What is the Big O time and space complexity of this code?"

    Common Mistakes

    Warning: 1. Keeping Constants: Saying "O(3N)" instead of simplifying to "O(N)".
    > 2. Confusing Different Inputs: If a function iterates over Array A (size N) and Array B (size M), the complexity is O(N + M), NOT O(N) or O(N²)!
    > 3. Assuming Every Loop is O(N): If a loop runs up to a fixed constant (e.g. for (int i = 0; i < 100; i++)), it is O(1), not O(N).

    Important Interviewer Tips

  • Clearly state variable names (e.g., "Let N be the number of nodes in the graph and E be the number of edges").
  • Mention both Best/Average/Worst case if relevant, but emphasize Worst Case.

    • 7. Summary

  • Big O measures upper bound worst-case asymptotic growth rate.
  • Drop constants: O(50N) \rightarrow O(N).
  • Keep dominant terms: O(N² + N) \rightarrow O(N²).
  • Multiple inputs: Use distinct variables like O(A + B) or O(A × B).

    • 8. Quiz

    Question 1: What is the Big O simplification of O(5N³ + 100N² + 10,000)? Answer: O(N³). Drop constants (5, 10,000) and keep only the highest dominant power term (N³).
    Question 2: What is the time complexity of a loop that runs from i = 1 to N, doubling i each step (i = i * 2)? Answer: O(log N). Because the loop variable doubles each step, it cuts the remaining iterations in half, taking logarithmic steps.
    Question 3: If a function takes two arrays of sizes M and N and uses two nested loops (outer over M, inner over N), what is the Big O complexity? Answer: O(M × N). Since the outer loop runs M times and the inner loop runs N times for each iteration of M, the total work is M multiplied by N.
    Question 4: Why do we focus primarily on worst-case Big O complexity in software engineering? Answer: Focusing on the worst-case guarantees that our system will perform within predictable upper bounds even under peak load or adverse input data.
    Question 5: What is the Big O complexity of accessing an element in an array by its index? Answer: O(1) constant time, because memory addresses are calculated directly via offset math without iterating over elements.