intermediate8 min read·Updated July 16, 2026

Big O Notation Explained: How to Analyze Algorithm Efficiency

Understand Big O notation with a clear mental model: growth rates and dominant terms. Follow a worked example deriving Big O from code, then practice with a nested loop function. Learn to predict real-world performance and avoid common pitfalls.

By Learnisim AI·Published July 16, 2026
LEARNING ARCWhy → Model → Worked example → Practice → Apply
PREREQUISITES
  • basic programming loops
  • understanding of functions
Big O Notation — Growth Rate Families Growth Rate Families (n = input size) 0 n ops O(1) constant O(log n) O(n) linear O(n log n) O(n²) Key: Doubling n → how much slower? O(n): 2× slower · O(n²): 4× slower · O(log n): +constant Worked Example: Max Product function maxProduct(arr) { let max = -Infinity; for (let i = 0; i < n; i++) { for (let j = i+1; j < n; j++) { let prod = arr[i] * arr[j]; if (prod > max) max = prod; } } return max; } Inner loop runs: (n-1)+(n-2)+...+1 = n(n-1)/2 Simplify: (n² - n)/2 → dominant term n² → O(n²) — Quadratic Time The Core Idea: Dominant Term T(n) = 4n³ + 2n² + 100n + 500 (operations for input size n) When n = 1000: 4n³ = 4 billion, others tiny Lower-order terms (n², n, constant) become irrelevant Big O = O(n³) — Cubic Growth Why It Matters: Predict Performance Algorithm n=100 n=1000 n=10⁶ O(1) constant 1 1 1 O(log n) 7 10 20 O(n) linear 100 1K 1M O(n²) quadratic 10K 1M 1T O(2ⁿ) exponential 10³⁰ — —
Big o notation overview diagram
Why

Why Big O Notation Matters: The Language of Algorithm Efficiency

Imagine you're sorting a list of 10,000 names. You write two different sorting functions. Both work correctly, but which one should you use? If you time them on your laptop, one might finish in 0.2 seconds, the other in 2 seconds. But what if you run them on a faster server? Or with 100,000 names? The raw time numbers become meaningless — they depend on the machine, the language, the compiler, even the weather (okay, maybe not the weather). Big O notation solves this by describing how the number of operations grows as the input size grows, ignoring constant factors and lower-order terms. It's the universal language for comparing algorithm efficiency, allowing you to say "this algorithm scales well" or "this one will choke on large inputs" without running a single benchmark. Without Big O, you're guessing. With it, you can reason about performance mathematically, before you even write the code.
Big O Notation — The Language of Algorithm Efficiency The Problem Raw time depends on: • Machine speed • Language / compiler • Input size (n) • Constant factors ❌ Unfair to compare raw times Big O Describes Growth How operations grow with input size n O(n²) → O(n log n) → O(n) Ignores constants & lower terms Focuses on dominant growth rate ✅ Universal comparison language Example Sort 10,000 names Bubble: O(n²) ~100M operations Merge: O(n log n) ~140K operations 700× fewer ops! How Algorithms Scale — Operations vs Input Size High Low Input size (n) Small Large O(n²) — Bad Bubble sort O(n log n) — Good Merge sort O(n) — Great Linear search O(1) — Best Hash lookup Key insight: Big O lets you predict performance before writing code — no benchmarks needed
Why Big O Notation Matters: The Language of Algorithm Efficiency diagram
Model

The Core Model: Growth Rates and Dominant Terms

Imagine you're measuring how long it takes to sort a deck of cards as the deck grows. A simple method like bubble sort might take roughly comparisons for cards, while a smarter method like merge sort takes about comparisons. Big O notation is a way to classify these growth patterns into families. s gets very large (like sorting a million cards), the term that grows fastest dominates everything else. For , when , the term is $3,000,000$ while is only $5,000$ — the part determines the shape of the curve. Big O drops constants (like the 3) and lower-order terms (like and $100$), leaving just . This gives us a high-level label for the algorithm's efficiency: constant , logarithmic , linear , linearithmic , quadratic , cubic , exponential , and factorial . Each represents a distinct growth rate family. The model is not about exact time — it's about scalability: how much slower does the algorithm get when you double the input size? For , doubling doubles the time; for , doubling quadruples the time; for , doubling adds a constant amount of time. This mental model lets you quickly reason about whether an algorithm will work for your expected data sizes.
Big O Notation — Growth Rate Families Core Idea: Dominant Term 4n³ + 2n² + 100n + 500 Dominant: 4n³ → O(n³) Drop constants & lower-order terms Focus on the fastest-growing term Growth Rate Families (n = input size) O(1) — Constant O(log n) — Logarithmic O(n) — Linear O(n log n) — Linearithmic O(n²) — Quadratic O(2ⁿ) — Exponential How Doubling Input Size Affects Time (n → 2n) Growth Rate Time at n Time at 2n Scalability Insight O(1) Constant 1 sec 1 sec No change O(log n) Log 1 sec ~1.3 sec + constant time O(n) Linear 1 sec 2 sec Doubles O(n²) Quadratic 1 sec 4 sec Quadruples Scaling matters
The Core Model: Growth Rates and Dominant Terms diagram
Worked example

Worked Example: Deriving Big O from Code Step by Step

Let's put the model into action with a concrete function. Consider this JavaScript function that finds the maximum product of any two numbers in an array:
javascript
function maxProduct(arr) {
  let max = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      let product = arr[i] * arr[j];
      if (product > max) {
        max = product;
      }
    }
  }
  return max;
}
Given: An array of length n.
Steps to derive Big O:
1.Identify the input size: n = arr.length.
2.Find the dominant operation: The innermost operation is the multiplication arr[i] * arr[j] and the comparison product > max. These happen inside the nested loops.
3.Count how many times the inner block runs: The outer loop runs n times. For each outer iteration i, the inner loop starts at j = i+1 and runs until j < n. So the number of inner iterations is:

- i=0: n-1 iterations
- i=1: n-2 iterations
- ...
- i=n-2: 1 iteration
- i=n-1: 0 iterations
Total = (n-1) + (n-2) + ... + 1 = n(n-1)/2.
4.Simplify to dominant term: n(n-1)/2 = (n² - n)/2. The fastest-growing term is n². Drop constants and lower-order terms → O(n²).
Result: This function has O(n²) time complexity. Doubling the array size roughly quadruples the runtime.
maxProduct(arr) function maxProduct(arr) { let max = -Infinity; for (let i = 0; i < n; i++) { for (let j = i+1; j < n; j++) { let product = arr[i] * arr[j]; if (product > max) max = product; } } return max; } n = arr.length Step 1: Input size = n n = arr.length Step 2: Dominant operation multiplication + comparison Step 3: Count iterations i=0 → n-1 iterations i=1 → n-2 iterations … → total = n(n-1)/2 Step 4: Simplify → O(n²) n(n-1)/2 = (n² − n)/2 → n² Result: O(n²) Double n → 4× runtime Takeaway: Nested loops over the same array → quadratic growth O(n²)
Worked Example: Deriving Big O from Code Step by Step diagram
Practice

Practice: Derive Big O from a Nested Loop Function

Now apply the same counting method from the worked example.
javascript
function countEvenSumPairs(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if ((arr[i] + arr[j]) % 2 === 0) {
        count++;
      }
    }
  }
  return count;
}
Your turn (try before reading further):
1. What is the input size ?
2. How many times does the inner block run as a function of ?
3.After dropping constants, what is the Big O time complexity?
Guided solution (check after you try):
The inner loop starts at , so each unordered pair is counted once. Total iterations: . Dominant term is → .
Apply

Applying Big O: Predicting Real-World Performance

You've learned to derive Big O from code. Now let's apply that skill to a realistic decision: choosing between two search algorithms for a large, unsorted dataset.
Scenario: You're building a contact list app. Users will search for a name among 10,000 contacts. You have two candidate functions:
•Linear Search: O(n) – checks each contact one by one.
•Binary Search: O(log n) – but requires the list to be sorted first (sorting is O(n log n)).
Given: The list is currently unsorted. Users will perform 1,000 searches per day.
Step 1 – Cost of each approach:
•Linear search: 10,000 checks per search × 1,000 searches = 10,000,000 checks.
•Binary search: Sort once (10,000 × log₂(10,000) ≈ 10,000 × 14 = 140,000 comparisons) + each search (log₂(10,000) ≈ 14 comparisons × 1,000 = 14,000) = total ~154,000 comparisons.
Step 2 – Compare: Binary search + sort is ~65× fewer comparisons for this workload. For a single search, linear might be fine; for many searches, the upfront sort pays off.
Step 3 – General insight: Big O helps you decide not just which algorithm is "faster" in theory, but which is better for your actual usage pattern. The dominant term (sort vs. linear) shifts based on how many times you search.

FAQ

What is Big O notation?
Big O notation describes the upper bound of an algorithm's runtime or space usage as input size grows, focusing on the dominant term and ignoring constants and lower-order terms.
When should I use Big O notation?
Use Big O to compare algorithm efficiency, especially for large inputs. It helps in choosing the best algorithm for performance-critical applications.
What are common pitfalls when deriving Big O?
Common pitfalls include forgetting to drop constants, ignoring lower-order terms, and misidentifying the dominant operation in nested loops.
How do I derive Big O from nested loops?
Count total iterations of the dominant work. Two nested loops each running about n times give roughly n² → O(n²). If the inner bound depends on i (triangular loops), the total is still proportional to n² after dropping constants, so it remains O(n²).
Can Big O predict exact runtime?
No, Big O predicts growth rate, not exact runtime. Actual performance depends on constants, hardware, and input specifics.