Big O Notation Explained: Time Complexity, Space Complexity, and Why They Matter in Interviews

Scenario context

Big O notation describes how an algorithm's resource usage grows as input size grows — not how fast it runs on your laptop. Learn to identify the 7 complexity classes (O(1) through O(n!)), derive time and space complexity by counting loops and stack frames, and communicate your analysis in three sentences that satisfy any FAANG interviewer.

Picture this: a candidate walks into a FAANG loop interview, gets a…

This walkthrough focuses on Why Your Correct Solution Might Still Get Rejected.

Before making a design choice, clarify:

• Picture this: a candidate walks into a FAANG loop interview, gets a duplicate-detection problem on a 10-element array, and writes a perfectly working solution.
• Two nested for loops, checking every pair.
• The interviewer nods and asks one question: "What's the time complexity of this solution?" The candidate stares at the code.

Concepts in play: jvm-internals-and-garbage-collection, sorting-and-searching-algorithms, database-indexing, graph-traversal-algorithms

Stage 1 — Big O From First Principles: The Language of Scale

• Before any formal definition, think about a library.
• Imagine you need to find a specific book.
• If the library is sorted alphabetically, you can open to the middle, decide which half your book is in, and repeat — halving the search space each time.
• If the library is completely unsorted and you must check every shelf, that is O(n).

Observable outcome: If the library is completely unsorted and you must check every shelf, that is O(n).

Stage 2 — What Big O Actually Measures: Growth Rate, Not Clock Time

• A common misconception: Big O measures how long your code takes to run.
• Two computers running the same O(n²) algorithm will show different millisecond times, but both exhibit the same shape of growth .
• Double the input, quadruple the work.
• That shape — the growth rate — is what Big O captures.

Observable outcome: That shape — the growth rate — is what Big O captures.

Stage 3 — The 7 Complexity Classes, Ranked from Best to Worst

• There are seven complexity families that cover the vast majority of algorithms you will encounter.
• The diagram below shows them ordered from most efficient (flat) to least efficient (explosive).
• The following flowchart reads left to right, from best to worst.
• Each node represents a complexity class.

graph LR
    A[" O(1) Constant"] --> B[" O(log n) Logarithmic"]
    B --> C[" O(n) Linear"]
    C --> D[" O(n log n) Linearithmic"]
    D --> E[" O(n) Quadratic"]
    E --> F[" O(2) Exponential"]
    F --> G[" O(n!) Factorial"]

    style A fill:#16a34a,color:#fff,stroke:#14532d
    style B fill:#65a30d,color:#fff,stroke:#3f6212
    style C fill:#ca8a04,color:#fff,stroke:#713f12
    style D fill:#ea580c,color:#fff,stroke:#7c2d12
    style E fill:#dc2626,color:#fff,stroke:#7f1d1d
    style F fill:#b91c1c,color:#fff,stroke:#450a0a
    style G fill:#7f1d1d,color:#fff,stroke:#3b0764

// O(1) — reading the first element, no matter how long the array is
public int getFirst(int[] arr) {
    return arr[0];   // single memory lookup — n doesn't matter
}

// O(1) average — HashMap lookup via hash function
public String getUsername(Map<Integer, String> users, int id) {
    return users.get(id);  // one hash computation, one bucket access
}

Observable outcome: Each node represents a complexity class.

Stage 4 — How to Derive Time Complexity in 4 Steps

• Deriving complexity is a mechanical process once you know the rules.
• Apply these four steps in order to any piece of code.
• The flowchart below maps out the exact decision process.
• Read it top-down: start by counting your loops, check whether they are nested, check whether the input halves, and arrive at your complexity class.

flowchart TD
    A([ Start: examine your code]) --> B{How many loops over n elements?}
    B -->|"Zero loops"| C[" O(1)  Constant No input traversal"]
    B -->|"One loop"| D{Does each iteration halve the remaining problem?}
    D -->|"Yes  e.g. binary search"| E[" O(log n)  Logarithmic"]
    D -->|"No  full traversal"| F{Does the loop body make a recursive call that also halves?}
    F -->|"Yes  e.g. merge sort"| G[" O(n log n)  Linearithmic"]
    F -->|"No"| H[" O(n)  Linear"]
    B -->|"Two nested loops"| I{Do both loops iterate over n?}
    I -->|"Yes"| J[" O(n)  Quadratic"]
    I -->|"Inner loop is constant size k"| K[" O(nk)  simplify to O(n)"]
    B -->|"Recursive branching factor of 2 at each call"| L[" O(2)  Exponential Add memoisation to fix"]

    style C fill:#16a34a,color:#fff
    style E fill:#65a30d,color:#fff
    style G fill:#ca8a04,color:#fff
    style H fill:#ca8a04,color:#fff
    style J fill:#dc2626,color:#fff
    style K fill:#ca8a04,color:#fff
    style L fill:#7f1d1d,color:#fff

Observable outcome: Read it top-down: start by counting your loops, check whether they are nested, check whether the input halves, and arrive at your complexity class.

Stage 5 — Space Complexity: The Resource Interviewers Forget to Ask About

• Time complexity gets all the attention, but space complexity is the other axis of the efficiency conversation — and interviewers frequently dock points for candidates who only address time.
• Definition: Space complexity measures how much extra memory an algorithm allocates as n grows.
• We ignore the input array itself (it already exists) and count only the auxiliary space — additional data structures, variables, and stack frames the algorithm creates.
• The question "Can you do it in O(1) extra space?" is a signal that the interviewer wants an in-place solution: no extra arrays, no hash maps, just a fixed number of pointer variables.

graph TD
    subgraph IT["Iterative Binary Search  O(1) extra space"]
        I1[One stack frame  while loop runs in place  no new frames added]
    end

    subgraph RB["Recursive Binary Search (n=1024)  O(log n) stack space"]
        R1["binarySearch(arr, 0, 1023)"] --> R2["binarySearch(arr, 0, 511)"]
        R2 --> R3["binarySearch(arr, 0, 255)"]
        R3 --> R4["binarySearch(arr, 0, 127)"]
        R4 --> R5["... 10 frames total (log 1024 = 10)"]
    end

    subgraph RF["Recursive fib(5)  O(n) stack depth on longest path"]
        F1["fib(5)"] --> F2["fib(4)"]
        F2 --> F3["fib(3)"]
        F3 --> F4["fib(2)"]
        F4 --> F5["fib(1)  base case 5 frames deep"]
    end

public void reverseInPlace(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];   // 3 variables total — O(1) regardless of n
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}
// Space: O(1) — only `left`, `right`, `temp` — three integers, constant regardless of n

Observable outcome: The question "Can you do it in O(1) extra space?" is a signal that the interviewer wants an in-place solution: no extra arrays, no hash maps, just a fixed number of pointer variables.

Stage 6 — Data Structure Complexities You Must Memorise

• Every data structure question in an interview implicitly tests whether you know the cost of the operations you're calling.
• When you choose a LinkedList over an ArrayList — or a TreeMap over a HashMap — the interviewer expects a complexity justification.
• \ Amortised O(1) for ArrayList.add() : most additions are O(1).
• Occasionally the backing array doubles in size (O(n) copy), but averaged across n additions the cost per addition is O(1).

Observable outcome: Occasionally the backing array doubles in size (O(n) copy), but averaged across n additions the cost per addition is O(1).

End-to-end outcome

After working through the stages, you should be able to explain:

• Counting lines of code instead of operations.
• A 3-line function with a hidden Collections.sort() call is O(n log n), not O(1).

Alternatives considered

The source focuses on one primary design. A second architecture is not compared, so no alternative is invented here.

Failure and degraded modes

Trade-offs & Failure Modes: When Complexity Analysis Misleads

• Detection: Where complexity analysis fails completely: I/O-bound systems.
• User or operator impact: Where complexity analysis fails completely: I/O-bound systems.