Chapter 1 — Big O, Time Complexity, Space Complexity, and Amortized Analysis

After this chapter, you will never again look at a piece of code the same way. Right now, when you write a function, you think about whether it works. After this chapter, you will also think about what happens to it when the data gets large — and you will be able to answer that question with precision, not intuition. That is what separates engineers who build things that scale from engineers who build things that collapse under real load. This chapter gives you the lens. Every chapter after this uses it.

Part 1: The Problem With Measuring in Seconds

Imagine you wrote a function on your laptop that searches through a list of 1,000 UPSC questions on AttemptIQ. You run it, and it takes 3 milliseconds. Your friend runs the same function on their older laptop and it takes 12 milliseconds. Your AWS server runs it and it takes 0.8 milliseconds.

Same function. Three different times. Which one is correct?

All of them are. And none of them tell you anything useful about the function itself.

This is the core problem: wall-clock time is a property of the machine, not the algorithm. If you measure performance in seconds, you are measuring your hardware, your CPU load, your compiler, your operating system scheduler — not the fundamental quality of your code.

So engineers stopped measuring in seconds. They started measuring in something that stays constant regardless of the machine: the number of operations the algorithm performs.

This is not an abstraction invented by academics. It is a practical necessity. When you are deciding between two approaches to searching through 10 million records in your PostgreSQL database, you do not have time to benchmark both on every possible machine. You need to reason about which one grows slower as the data grows. That reasoning requires a machine-independent measure.

The measure is called Big O notation, but let's understand what it actually is before we attach the name.

Part 2: Counting Operations, Not Seconds

Let's write the simplest possible function: finding whether a number exists in a list.

function contains(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return true;
  }
  return false;
}

Forget seconds. Ask instead: how many comparisons does this function make?

If arr has 1 element, it makes at most 1 comparison. If arr has 10 elements, it makes at most 10 comparisons. If arr has 1,000 elements, it makes at most 1,000 comparisons. If arr has n elements, it makes at most n comparisons.

Notice what just happened: the number of operations is directly tied to the size of the input. We gave the input a name — n — and described the work as a function of n. The work grows linearly with the input. Double the input, double the work.

Now ask a different question about a different function:

function getFirst(arr) {
  return arr[0];
}

How many operations does this make?

If arr has 1 element: 1 operation. If arr has 10 elements: 1 operation. If arr has 1,000 elements: 1 operation. If arr has n elements: 1 operation.

The work does not change regardless of input size. It is constant.

These are two fundamentally different behaviors. The first function's work grows with input. The second function's work doesn't. This difference — how the work grows as input grows — is what we are measuring when we talk about algorithmic complexity.

Now we can attach the name: Big O notation is a way of describing this growth rate, using n to represent the size of the input.

• Constant work regardless of input → written as O(1) (read: "order one" or "constant time")
• Work that grows linearly with input → written as O(n) (read: "order n" or "linear time")

The "O" stands for "Order of", borrowed from mathematics. It means: "the growth rate is on the order of..."

Part 3: Why We Throw Away Constants and Small Terms

You might be thinking: "But contains doesn't just do one comparison per element. It also increments i, checks i < arr.length, and does a few other things. Shouldn't we count those too?"

You are right to notice this. Let's count more carefully. For each element in the array, contains does:

1. Compare i < arr.length (1 operation)
2. Compare arr[i] === target (1 operation)
3. Increment i++ (1 operation)

So it is actually 3 operations per element, meaning the total is 3n operations, not just n.

But here is the key insight: when n gets large, the constant multiplier stops mattering.

If n = 1,000,000:

• n = 1,000,000 operations
• 3n = 3,000,000 operations

That factor of 3 feels significant. But now compare it to an algorithm that does n² operations:

• n² = 1,000,000,000,000 operations (one trillion)

At that scale, whether you have n or 3n or even 100n is irrelevant. The shape of the growth is what dominates. A trillion is incomparably worse than three million, regardless of that factor of 3.

So Big O notation deliberately strips out constants and focuses purely on the shape of the growth curve. When we write O(n), we mean "grows linearly" — not "grows at exactly n steps." The constant multiplier is noise compared to the growth rate.

The same logic applies to multiple terms. If a function does n² + n operations:

• When n = 1,000: n² = 1,000,000 and n = 1,000. The n term contributes 0.1% of the total. It is noise.
• We keep only the dominant (fastest-growing) term: O(n²).

This is not sloppiness. It is deliberate. Big O tells you about growth at scale, and at scale, only the dominant term matters.

Part 4: The Growth Curves You Will See Everywhere

There are a handful of growth rates that cover nearly every algorithm you will encounter. Let us derive each one from a concrete scenario rather than memorizing them as a list.

O(1) — Constant

You access arr[42]. Regardless of how large the array is, the CPU computes start_address + (42 × element_size) and jumps directly there. One arithmetic calculation. Done. The array could have 10 elements or 10 billion — the access takes the same time.

Work does not grow with input. The graph is a flat horizontal line.

O(log n) — Logarithmic

You have a sorted array of 1,000 numbers and you want to find a specific one. Instead of checking every element, you check the middle element. If your target is smaller, you discard the right half and check the middle of the left half. If larger, discard the left half.

Every single check cuts the remaining search space in half.

• Start with 1,000 elements
• After 1 check: 500 remain
• After 2 checks: 250 remain
• After 3 checks: 125 remain
• After 10 checks: ~1 element remains

How many times can you cut 1,000 in half before you reach 1? The answer is log₂(1000) ≈ 10.

In general: if n = 1,000,000, you need at most log₂(1,000,000) ≈ 20 checks. You are doing 20 operations on a million-element input. This is extraordinarily efficient.

The graph is a curve that rises steeply at first and then flattens to nearly horizontal. It grows, but barely.

(We will build this algorithm properly in Chapter 9 — Binary Search. For now, just understand the shape.)

O(n) — Linear

Your contains function above. You look at each element once. If n doubles, the work doubles. The graph is a straight diagonal line.

O(n log n) — Linearithmic

Efficient sorting algorithms like merge sort and quicksort do roughly n log n operations. We will derive this precisely in Chapter 4 (Recursion), where we build merge sort step by step. For now: it is slightly worse than linear, much better than quadratic. The graph is a gentle curve above the straight O(n) line.

O(n²) — Quadratic

You have a list of users and you want to find every pair of users who share a birthday. The brute-force approach: take user 1, compare to users 2 through n. Take user 2, compare to users 3 through n. And so on.

For n users:

• User 1 makes n-1 comparisons
• User 2 makes n-2 comparisons
• ...
• User n-1 makes 1 comparison

Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 comparisons.

Strip the constant (the /2): O(n²).

The signature of O(n²) is a loop inside a loop, where both loops run relative to n. When you see that pattern, you should immediately think "quadratic — is there a way to eliminate the inner loop?"

If n = 10,000 users: n² = 100,000,000 comparisons. That starts to be slow. If n = 1,000,000 users, it is a trillion comparisons. It will not finish in your lifetime.

The graph curves sharply upward — a parabola.

O(2ⁿ) — Exponential

Calculating all possible subsets of a set, or naive recursive Fibonacci. Every time you add one element to the input, the work doubles. At n=10: 1,024 operations. At n=30: over one billion. At n=50: over one quadrillion.

This is the growth rate that makes computers helpless. You will encounter it in recursion and backtracking, and part of the art of those topics is recognising when you are accidentally doing exponential work.

Here is all five growth rates on a single conceptual graph. The x-axis is input size n, the y-axis is operations:

Operations
    |
    |                                             O(2ⁿ)
    |                                        ,,/
    |                                   ,,,/
    |                              ,,,/       O(n²)
    |                        ,,,,/       ,,,/
    |                   ,,,/        ,,/
    |              ,,,,/       ,,/         O(n log n)
    |         ,,,,/      ,,,/          ,/
    |    ,,,,/      ,,,,/           ,/     O(n)
    |,,,/      ,,,/             __/
    |     ,,,,/            ___/           O(log n)
    |,,,,/           _____/           ___________
    |           ____/                              O(1)
    +-------------------------------------------------> n (input size)

At small n, these curves look similar. At large n, the difference is astronomical. A function that scans your entire PostgreSQL table on every request (O(n)) might be fine at 100 rows. At 10 million rows, it will time out. This is why senior engineers think about growth rates — not because they are academic, but because systems fail at scale when these curves are ignored.

Part 5: Best Case, Worst Case, Average Case — And Why We Almost Always Care About Worst Case

Go back to contains:

function contains(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return true;
  }
  return false;
}

Three scenarios:

Best case: The target is arr[0]. We find it on the first comparison and return immediately. 1 operation regardless of n. O(1) best case.

Worst case: The target is not in the array, or it is the last element. We check all n elements. O(n) worst case.

Average case: Assuming the target is equally likely to be anywhere, on average we check n/2 elements. O(n/2) → strip the constant → O(n) average case.

When engineers say "this function is O(n)", they almost always mean worst case. Why?

Because systems fail at their worst case, not their average case. If you are designing AttemptIQ's search, you cannot say "well, on average it is fine." The user whose query triggers the worst case will have a broken experience. You design for the worst case.

There is a formal name for worst case: Big O (written O). There are also formal notations for best case (Ω, "Big Omega") and average case (Θ, "Big Theta"), but in practice and in interviews, "Big O" almost always means worst case, and that is the one you will use.

Part 6: Space Complexity — The Other Axis

Everything we have discussed so far is time complexity — how many operations does the algorithm perform?

But there is a second resource algorithms consume: memory. This is space complexity, and it follows exactly the same analytical framework. You count not operations, but memory allocations, and express them as a function of n.

Let's trace through a concrete example.

function doubleAll(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

Time complexity: We loop through n elements once, doing constant work each time. O(n) time.

Space complexity: We allocate a new array result and push n elements into it. The memory we use grows linearly with n. O(n) space.

Now a different version:

function doubleAllInPlace(arr) {
  for (let i = 0; i < arr.length; i++) {
    arr[i] = arr[i] * 2;
  }
  return arr;
}

Time complexity: Same loop, O(n) time.

Space complexity: We create no new arrays. We only use one loop variable i, which is a single integer — constant space regardless of n. O(1) space.

Two algorithms, identical time complexity, different space complexity. Which is better? It depends on your constraints:

• If the caller cannot have their original array mutated (e.g., it is shared state in a React component), you must use the first version, accepting O(n) space.
• If memory is tight (say you are processing a 2GB file on a server), the second version is essential.

This is why you must analyze both dimensions. An algorithm that is O(1) space but O(n²) time might be worse than one that is O(n) space but O(n log n) time. You are always making a trade-off between time and space. Recognizing that you have this trade-off is the first step to making it consciously.

An important clarification about what counts as space:

Space complexity measures the extra memory your algorithm allocates — not the memory used by the input itself. The input already exists before your function runs. We only count what your function additionally allocates.

This is why getFirst(arr) is O(1) space even though arr might be huge — the function allocates nothing new, it just reads from existing memory.

Part 7: Amortized Complexity — The "Sometimes Expensive" Problem

There is a scenario that breaks naive complexity analysis: when most operations are cheap, but occasionally one operation is very expensive.

You experience this every time you use JavaScript arrays.

Here is what most JavaScript developers don't know: when you call arr.push(element), it is not always O(1).

To understand why, you need to understand what an array actually is in memory.

An array is a contiguous block of memory. If you create const arr = [1, 2, 3], the JavaScript engine allocates three consecutive memory slots. Something like this:

Memory address 1000: [ 1 ]
Memory address 1001: [ 2 ]
Memory address 1002: [ 3 ]

Now you call arr.push(4). The engine needs to put 4 at address 1003. If that address happens to be free, it writes there. O(1). Done.

But what if address 1003 is already occupied by something else — another variable, another object? The engine cannot simply overwrite it. That memory belongs to someone else.

The engine must:

1. Allocate a new, larger block of memory elsewhere — say, double the size: 6 slots.
2. Copy all 3 existing elements into the new block. (3 copy operations)
3. Write the new element in slot 4.
4. Free the old 3-slot block.

That single push just cost O(n) — it copied all n existing elements.

So push is sometimes O(1) and sometimes O(n). What is its complexity?

This is where amortized analysis comes in. The word "amortized" comes from finance — it means spreading a large cost across many smaller transactions. A mortgage is amortized: you pay a little each month rather than the full house price at once.

Here is the key observation: the expensive O(n) copy happens rarely. And every time it happens, the engine doubles the array's capacity, meaning it will not happen again until you have pushed n more elements.

Let's count the total work for n push operations on a starting-empty array, assuming the engine doubles capacity each time it resizes:

• Pushes 1: capacity = 1. Push the 1st element. Cost: 1.
• Push 2: full, must resize. Allocate 2 slots, copy 1 element, push. Cost: 1 (copy) + 1 (push) = 2. Capacity now 2.
• Push 3: full, must resize. Allocate 4 slots, copy 2 elements, push. Cost: 2 + 1 = 3. Capacity now 4.
• Pushes 4: free slot available. Push. Cost: 1.
• Push 5: full, must resize. Allocate 8 slots, copy 4 elements, push. Cost: 4 + 1 = 5. Capacity now 8.
• Pushes 6, 7, 8: free slots. Cost: 1 each.
• Push 9: full, must resize. Allocate 16 slots, copy 8 elements. Cost: 8 + 1 = 9.

The resize costs are: 1, 2, 3, 5, 9, 17... which follow the pattern 1 + 2 + 4 + 8 + 16 + ...

After n total pushes, the resize costs sum to at most 2n (a geometric series — the sum of 1 + 2 + 4 + ... + n/2 is at most 2n).

Add the n regular push costs: total work = n (regular) + 2n (resizes) = 3n operations for n pushes.

Average cost per push = 3n / n = 3 → O(1) amortized.

Each individual push is amortized O(1), even though some individual pushes cost O(n). The expensive operations are rare enough, and the cheap operations frequent enough, that the average cost per operation remains constant.

This is why arr.push() is listed as O(1) amortized in every reference, and why JavaScript arrays feel fast in practice even though they occasionally do heavy copying.

When to think about amortized complexity: Whenever you see an operation that "usually" does constant work but "sometimes" does more — resizing, rehashing, garbage collection pauses. The amortized analysis tells you whether the "sometimes expensive" operation dilutes badly across a sequence, or stays cheap on average.

Part 8: The Four-Question Framework Applied

Before you write any algorithm, ask these four questions in order. We will use them on every problem in this book. Here is what they mean in the context of complexity:

Question 1: What do I have? Understand your input. What is n? Is n the length of an array? The number of nodes in a tree? The number of characters in a string? You cannot reason about complexity without first naming what n is.

Question 2: What do I want? Understand your output. Return a boolean? A new array? A single number? This shapes what kind of work you need to do.

Question 3: What is the brute force? Write the simplest correct solution first. Do not optimize. Then analyze its complexity by counting operations. This gives you a baseline — the complexity you are trying to beat.

Question 4: Where is the waste? Look at your brute force. What work is it doing repeatedly that it didn't have to? A nested loop doing n² comparisons — can you avoid the inner loop with a different data structure? Are you recomputing the same value multiple times?

Every optimization in this book is the answer to Question 4. Every clever algorithm is someone who found the waste.

Let's apply all four questions right now:

Problem: Given an array of numbers, return true if any two numbers in the array add up to a target sum.

arr = [3, 7, 1, 9, 2], target = 10
Answer: true (1 + 9 = 10)

Q1: What do I have? An array of n numbers and a target integer.

Q2: What do I want? A boolean: true if any pair sums to target, false otherwise.

Q3: What is the brute force? Check every pair. For each number, check it against every other number.

function hasPairSum(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) return true;
    }
  }
  return false;
}

Complexity: For n elements, the outer loop runs n times, the inner loop runs up to n times. Total: approximately n²/2 comparisons → O(n²) time, O(1) space.

Q4: Where is the waste? For each element arr[i], we are searching the rest of the array for its complement (target - arr[i]). That search is O(n) — we scan through every remaining element.

The waste is: we are doing a linear search for the complement every single time.

What if, instead of scanning the rest of the array, we could check in O(1) whether the complement already exists? We would need a data structure that can answer "does this value exist?" in constant time.

That data structure exists. It is called a HashMap (or a Set for this specific problem). We have not studied it yet — that is Chapter 3. But right now you can feel why it will be powerful: it eliminates the inner loop entirely, turning O(n²) into O(n).

This is the pattern. First-principles complexity analysis reveals the waste. A better data structure eliminates the waste. You will see this exact arc in every chapter that follows.

Part 9: How to Think About This, Not Just Use It

When you are in an interview and you see a problem, complexity analysis is not something you do after you code. It is something you do while you are understanding the problem, before you write a single line.

Here is the signal to watch for: the size of the input tells you what complexity is acceptable.

This is not a rule to memorize — it is a physical reality. Here is the reasoning:

Modern computers execute roughly 10⁸ to 10⁹ simple operations per second. Interviews typically expect solutions that run in about 1 second. That means you have roughly 10⁸ operations to spend.

Now, given input size n:

• If n ≤ 10: you can afford O(2ⁿ) — exponential is fine.
• If n ≤ 1,000: you can afford O(n²) — quadratic is fine.
• If n ≤ 100,000: you can afford O(n log n).
• If n ≤ 10,000,000: you need O(n).
• If n is unlimited or the operation is called continuously: you need O(1) or O(log n).

Interviewers often signal this by telling you the input size. If they say "the array has up to 10⁵ elements," they are telling you that O(n²) will not pass — you need at least O(n log n). This is a clue, not a coincidence.

When you do not know the input size, state your assumption out loud: "I'm assuming n could be large, so I want to aim for O(n) or better." This demonstrates that you think in terms of growth, not just correctness.

Part 10: Where Big O Lives in Real Systems

This is not theory. Every production system you will work with uses these concepts explicitly.

PostgreSQL's Query Planner

When you run a SQL query on AttemptIQ — say, fetching all questions a user has attempted — PostgreSQL does not blindly execute your query. It first runs a query planner that estimates the cost of multiple execution strategies and picks the cheapest one.

The query planner estimates costs in terms that are direct analogs of Big O: sequential scan cost (proportional to number of rows, i.e., O(n)), index scan cost (proportional to log of rows, i.e., O(log n)), and hash join cost (O(n + m) for two tables of sizes n and m). When you run EXPLAIN ANALYZE on a query, PostgreSQL shows you these estimates alongside the actual measured costs.

When you do not have an index on a WHERE column, PostgreSQL performs a sequential scan — it reads every page of the table from disk. At 1,000 rows, unnoticeable. At 10,000,000 rows, catastrophic. The index turns O(n) into O(log n) by maintaining a B-tree structure that allows binary-search-like navigation through the data. You are trading O(n) extra space (the index) for O(log n) query time. This is the time-space trade-off made concrete in a system you are already using.

Redis's O(1) Guarantee

Redis advertises that GET and SET operations are O(1). This is not a marketing claim — it is a direct consequence of Redis using a hash table as its primary data structure. When you call redis.get('user:123:session'), Redis computes a hash of the key, finds the bucket in constant time, and retrieves the value. The number of keys in Redis does not affect this lookup time. This is why Redis is used as a cache — not just because it is in memory, but because its fundamental data structure guarantees constant-time access regardless of dataset size.

Redis's LRANGE (list range) operation is O(n) where n is the number of elements returned — not the total list size. This is an important nuance: the complexity depends on what you are asking for, not just what is stored.

V8's Array Implementation and Amortized Push

The JavaScript engine in Node.js and Chrome is V8. V8 implements JavaScript arrays as one of two underlying structures depending on usage: a fast array (a true contiguous C++ array, fixed-size under the hood) or a dictionary array (a hash map, used when arrays have sparse indices like arr[10000] = 5 with nothing in between).

When you push elements onto a fast array and it fills up, V8 uses a growth factor of approximately 1.5× (not exactly 2×, because 2× wastes too much memory at large sizes, but the amortized analysis holds regardless of the growth factor as long as it is a constant multiplier). This is exactly the doubling strategy we analyzed in Part 7. The amortized O(1) push cost is not an approximation — it is a mathematical consequence of this growth strategy, baked into V8's source code.

If you ever do arr[1000000] = 5 on an otherwise empty array, V8 switches to a dictionary (hash map) representation to avoid allocating a million slots of memory. Subsequent pushes on that array behave differently because it is no longer a contiguous block. This is why accessing arr[0] on a "normal" array is O(1), but the same operation on a sparse array can be O(1) for a different reason (hash lookup) — with slightly different constant factors.

Cloudflare's Rate Limiter

Cloudflare's edge network enforces rate limits: e.g., no more than 100 requests per IP per minute. A naive implementation would store every request timestamp and scan through them to count recent requests — O(n) per check where n is the number of stored timestamps.

Cloudflare instead uses a technique called the sliding window counter, which reduces this to O(1) per check by maintaining only two counters (current window count and previous window count) and a mathematical interpolation. The difference between O(n) and O(1) here is the difference between rate limiting being feasible at Cloudflare's scale (trillions of requests) and being impossible. This is Big O as an engineering requirement, not an academic exercise.

Vocabulary Map

Practice Problems

Work through each problem on paper before writing any code. The goal is reasoning, not running.

Problem 1 — Trace and Predict

Here is a function:

function mystery(n) {
  let count = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = i; j <= n; j++) {
      count++;
    }
  }
  return count;
}

Your task: Without running this code, trace through it for n = 4. Write out the exact value of count at each step of both loops. Then determine what mystery(4) returns. After that, figure out what mystery(n) returns in general, and derive its time complexity from your trace — not by guessing, but by showing the arithmetic of why.

Hint: Notice that the inner loop does not start at 1 — it starts at i. What does this change about the total number of iterations compared to a loop that always starts at 1?

Problem 2 — Find the Waste

Here is a function that checks whether a string is a palindrome (reads the same forwards and backwards):

function isPalindrome(s) {
  for (let i = 0; i < s.length; i++) {
    if (s[i] !== s[s.length - 1 - i]) return false;
  }
  return true;
}

Part A: What is the time complexity of this function? Derive it — do not just state it. Show what n is, what operation is repeated, and how many times.

Part B: This function has a subtle waste. It checks every character once — but does it actually need to check every character? At what point can it stop? Rewrite the function to eliminate this waste, and derive the complexity of your improved version.

Part C: Did your optimization improve the Big O complexity? If not — why not? What does this tell you about the relationship between Big O and actual performance?

(This problem teaches something important: eliminating waste does not always change the Big O class. But it still matters. The constant factor improved, even though the notation stays the same. Remember: Big O hides constants.)

Problem 3 — Failure Analysis

A junior developer on your ScoreResume team writes the following function to check if a user's resume score has improved compared to their previous score. The function is called every time a user views their dashboard — potentially millions of times per day.

function hasImproved(userId, scores) {
  // scores is an array of ALL scores for ALL users, sorted by timestamp
  // Each element: { userId, score, timestamp }
  
  const userScores = [];
  for (let i = 0; i < scores.length; i++) {
    if (scores[i].userId === userId) {
      userScores.push(scores[i]);
    }
  }
  
  if (userScores.length < 2) return false;
  
  const latest = userScores[userScores.length - 1];
  const previous = userScores[userScores.length - 2];
  return latest.score > previous.score;
}

Your task:

1. What is n in this function? (Be precise — n is not just "the input". Name it specifically.)
2. What is the time complexity? Derive it.
3. The function is called once per dashboard view. If ScoreResume grows to 500,000 users, each viewing their dashboard 3 times per day, and the scores array grows to 10,000,000 entries — what happens? Give a rough estimate of total daily operations.
4. Identify the exact line where the waste is concentrated.
5. Describe (in plain English, no code required) a better data structure or data organization strategy that would make this function faster. What would the new complexity be?

Problem 4 — Design Under Constraints

You are designing the analytics backend for AttemptIQ. Every time a user answers a question, you need to:

• Record the attempt (userId, questionId, isCorrect, timestamp)
• Update the user's per-subject accuracy in real-time
• Answer the query "what is User X's current accuracy in Subject Y?" in under 10ms, regardless of how many total attempts exist in the system

The system currently has 50,000 users and 10,000,000 total attempts. It is expected to grow to 500,000 users and 500,000,000 attempts within 18 months.

Your task: Design the data storage strategy for this system. You may not use a brute-force "scan all attempts" approach. For each decision you make:

1. State the data structure or schema design decision.
2. Derive the time complexity for the read query ("what is User X's accuracy in Subject Y?").
3. Derive the time complexity for the write operation (recording a new attempt and updating accuracy).
4. Identify any space trade-offs you are making.

You do not need to write code. Write in plain English with enough precision that another engineer could implement it. Justify every decision using complexity reasoning.

Problem 5 — Reach Beyond

This problem asks you to reason beyond what was explicitly taught.

You know that:

• O(log n) algorithms typically work by cutting the problem in half on each step
• O(n) algorithms typically work by visiting each element once
• O(n²) algorithms typically have a loop inside a loop

Here is a function:

function countPairs(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === 0) {
        count++;
      }
    }
  }
  return count / 2; // divide by 2 because each pair is counted twice
}

Part A: Derive the time complexity. Show your work.

Part B: Here is a claim: "This function can be made O(n log n) by sorting the array first and then using a smarter search." You have not studied sorting in depth yet. But based on what you know about O(log n) and O(n), can you reason about why sorting might help here? What property of a sorted array could be exploited to avoid the inner loop?

Part C (connection to this chapter's core idea): The amortized analysis in Part 7 used the idea that occasionally expensive operations are "paid for" by many cheap ones. Can you think of a real scenario in your own products — AttemptIQ or ScoreResume — where an operation might be amortized in this sense? Describe it concretely: what is the "occasionally expensive" operation, what makes it expensive, and why does it not make the system slow in practice?

(There is no single correct answer to Part C. The goal is to transfer the concept to your own mental model. An answer that shows genuine reasoning about your product is better than a technically perfect but generic answer.)

What's Coming Next

Everything in this chapter was about measuring and comparing. You now have the lens. But a lens without anything to look at is useless. In Chapter 2, we will look at the first and most fundamental data structure: the array. Not JavaScript's [] — we are going one layer deeper, to the contiguous block of memory that every array in every language is built on top of. You will understand why array access is O(1), why insertion in the middle is O(n), and why JavaScript's [] is both more and less than a "real" array. Most importantly, you will solve your first real algorithm problems with this new complexity lens and feel exactly what it means when an O(n²) solution becomes O(n) by choosing a better structure.