Analysis Techniques

Appending to a Python list or JavaScript array almost always feels instantaneous, yet every so often the structure allocates a fresh buffer and copies every element into it, an `O(n)` operation. So why do textbooks still call append `O(1)`? Because amortized over a long sequence of appends, the rare expensive operation is paid for by many cheap ones. **Amortized Analysis** is the formal machinery that makes this kind of argument rigorous. This lesson teaches the three classical methods. The **aggregate method** sums the total cost of `n` operations and divides by `n` for a per-operation bound. The **accounting (banker's) method** charges each operation a fixed amount and stores credits on the data structure to pay for future expensive ones. The **potential (physicist's) method** defines a potential function `Phi` and computes amortized cost as actual cost plus the change in `Phi`. You will apply all three to dynamic array doubling, stacks with multipop, and binary counters, and see how amortized `O(1)` differs from worst-case `O(1)` and from average-case analysis. This lesson stands on the shoulders of **Big-O Notation (Upper Bound)** and **Time Complexity Analysis Techniques**. From those lessons you can already analyze a single operation; amortized analysis is what you reach for when the cost of *one* operation is misleading and the right object of study is a *sequence* of operations. Next you will move to **Recurrence Relations**, the other major analysis tool, used when an algorithm's cost is most naturally written recursively rather than as a running total.

When you stare at merge sort or binary search, the running time is not naturally a simple sum like `n^2/2 + n/2`. It is something more interesting: the cost of a problem of size `n` is built out of the cost of smaller problems plus a little glue. That self-referential structure is captured by a **recurrence relation**, an equation of the form `T(n) = ...` written in terms of `T` on smaller inputs. This lesson teaches you to spot, write, and classify recurrences directly from recursive code. You will identify the two ingredients every recurrence needs (the recursive case and the base case), then translate familiar algorithms into their `T(n)` equations: factorial gives `T(n) = T(n-1) + 1`, binary search gives `T(n) = T(n/2) + 1`, merge sort gives `T(n) = 2 T(n/2) + n`, and naive Fibonacci gives `T(n) = T(n-1) + T(n-2) + 1`. You will also group recurrences into three families (linear, divide-and-conquer, and multi-branch) and recognize the Big-O class each typically produces. This lesson builds on **Big-O Notation (Upper Bound)**, which gave you the language for expressing complexity, and on **Mathematical Sequences**, which gave you experience with arithmetic, geometric, and Fibonacci-style sequences, exactly the patterns you will see when a recurrence is expanded. Writing a recurrence is half the battle; the other half is converting it into a closed-form Big-O. That is the subject of the very next lesson, **Solving Recurrence Relations**.

Writing the recurrence `T(n) = 2 T(n/2) + n` for merge sort is the easy part. Turning it into the closed-form `O(n log n)` is where the real algorithm analysis happens, and it is exactly what this lesson is for. **Solving Recurrence Relations** gives you a small toolkit that, used well, can analyze nearly every recursive algorithm you will meet in interviews, papers, or production. This lesson walks through five methods. The **Substitution Method** has you guess the solution and prove it by induction, useful when you already suspect the bound. The **Recursion Tree Method** visualizes work level by level and sums it; this is how you see why merge sort spends `n` work per level over `log_2(n)` levels. The **Master Theorem** mechanically solves the divide-and-conquer form `T(n) = a T(n/b) + f(n)` via three cases, and you will memorize when each case fires. The **Extended Master Theorem** patches the gap when `f(n)` includes logarithmic factors. The **Akra-Bazzi Method** generalizes to unequal subproblem sizes that the basic theorem cannot handle. You will practice picking the right tool for each recurrence rather than blindly reaching for the same one every time. This lesson directly continues **Recurrence Relations**, where you learned to write `T(n)` from recursive code, and reuses ideas from **Big-O Notation (Upper Bound)** and **Mathematical Sequences** for the underlying summation arguments. With the analysis sub-track complete, you will pivot back to advanced math in **Modular Arithmetic**, where number-theoretic tools meet algorithm design.

Recognizing `O(n)` or `O(n^2)` on a slide is one thing; staring at unfamiliar code in an interview and confidently announcing its complexity is another. The gap between those two skills is filled by analysis technique, and that technique is what this lesson hands you. **Time Complexity Analysis Techniques** turns Big-O classification into a repeatable workflow you can apply to any snippet. You will analyze single loops with non-standard step sizes, nested loops where the inner bounds depend on the outer variable, sequential blocks that you sum and simplify, `if`/`else` branches where you take the worst case, and the telltale halving-or-multiplying patterns that produce `O(log n)`. Along the way you will see why a triangular loop summing `0 + 1 + 2 + ... + (n-1)` lands at `O(n^2)`, and why constant-bounded loops collapse to `O(1)` no matter how many times they run. In **Big-O Notation (Upper Bound)**, you learned what `O(f(n))` means and how to spot the dominant term in a polynomial. This lesson sharpens that recognition into a procedure: count iterations precisely, multiply for nesting, add for sequencing, and drop everything but the dominant term. Once you can dissect time complexity from real code, you will be ready for **Space Complexity Fundamentals**, where you apply the same Big-O lens to memory usage instead of operation counts.