Time Complexity

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.

How can you tell which of two algorithms will scale to a million inputs without ever running them on real hardware? Wall-clock timing fails this test because it depends on your CPU, your language, and even what other apps are open, so we need a more durable measure of efficiency. The word *asymptotic* looks intimidating, but the idea behind it is simple: it describes how a function behaves as its input grows very large. **Asymptotic Analysis Fundamentals** uses that idea to build a hardware-independent measure of efficiency — by counting how the number of operations an algorithm performs grows as the input size `n` increases, you get a yardstick that works regardless of your CPU, language, or environment. You will see why basic operation counting beats stopwatch timing, how growth rates rank from constant to exponential, why constant factors and lower-order terms drop out of the analysis, and what it really means for `n` to represent the size of an input. In **Counting Operations**, you built the habit of tracing through code and tallying how many steps it performs as input size `n` grows. Every operation count you produced there — a loop running `n` times, nested loops running `n * n` times — becomes exactly the formula this lesson formalizes. Asymptotic analysis is the language that turns those raw counts into a precise, hardware-independent way to compare algorithms. Once you are comfortable thinking in growth rates, you will be ready for **Big-O Notation (Upper Bound)**, the formal symbolic language (think `O(n)`, `O(n^2)`, `O(log n)`) used everywhere in textbooks, interviews, and engineering documentation to express the ideas you build here.

How do you compare two solutions to the same problem without ever running them on real hardware? Big-O is the symbolic shorthand that the entire industry uses to do exactly that, and it is the single most referenced notation in textbooks, technical interviews, and engineering documentation. **Big-O Notation (Upper Bound)** turns the growth-rate ideas you have been thinking about into precise notation. You will see what `O(f(n))` formally means as an upper bound, walk through the seven complexity classes you will meet again and again (`O(1)`, `O(log n)`, `O(n)`, `O(n log n)`, `O(n^2)`, `O(2^n)`, `O(n!)`), and learn the rules for reading Big-O straight from code: single loops, nested loops, sequential blocks, conditional branches, and inputs with multiple variables like `O(n + m)` and `O(n * m)`. You will also meet best, worst, and average case analysis so you know which scenario a Big-O statement is describing. In **Asymptotic Analysis Fundamentals**, you saw why we count operations as a function of input size `n`, why constants and lower-order terms drop away, and how growth rates rank from constant to exponential. Big-O is the formal language for everything you reasoned about there: each growth-rate intuition becomes a concrete `O(...)` expression. Once you can classify code by sight, you will be ready for **Time Complexity Analysis Techniques**, where you will apply these rules to longer, more realistic snippets and develop a systematic analysis workflow.

If `O(n)` is the worst-case ceiling on an algorithm's running time, what tells you the floor, the absolute minimum work the algorithm must always do? That is the question **Big-Omega Notation** answers, and it is the second pillar of asymptotic analysis that turns half a description of performance into the full picture. This lesson introduces `Omega(g(n))` as a formal lower bound, with the mirror-image definition of Big-O: there exist positive constants `c` and `n0` such that `f(n) >= c * g(n)` for all `n >= n0`. You will practice proving Omega claims, analyze the best-case behavior of familiar algorithms (linear search, bubble sort, insertion sort), and meet a famous problem lower bound: any comparison-based sort must do at least `Omega(n log n)` comparisons in the worst case. You will also learn to spot when an algorithm is asymptotically optimal because its upper and lower bounds coincide. This lesson builds directly on **Big-O Notation (Upper Bound)**, where you learned to express upper bounds on growth using constants `c` and `n0`. Big-Omega flips the inequality from `<=` to `>=` and reuses the same machinery to describe floors instead of ceilings. Once you are comfortable bracketing algorithms with both bounds, you will be ready for **Big-Theta Notation (Tight Bound)**, where the upper and lower bounds meet to give the most precise complexity statement possible.

When you can say *both* that an algorithm runs in `O(n log n)` and that it must do at least `Omega(n log n)` work, the ceiling and floor have collapsed onto the same growth rate. That coincidence is the most informative complexity statement you can make, and it is what **Big-Theta Notation** captures in a single symbol. This lesson defines `Theta(g(n))` as the intersection of Big-O and Big-Omega: there exist positive constants `c1`, `c2`, and `n0` such that `c1 * g(n) <= f(n) <= c2 * g(n)` for all `n >= n0`, the so-called sandwich property. You will practice classifying functions and algorithms by their tight bound, learn when Big-Theta is appropriate (best and worst case have the same growth rate) versus when only Big-O is honest (the cases differ), and see why merge sort is `Theta(n log n)` while linear search is *not* Theta of any single function. This lesson stitches together two ideas you have already met. From **Big-O Notation (Upper Bound)** you have the ceiling `f(n) <= c * g(n)`, and from **Big-Omega Notation (Lower Bound)** you have the floor `f(n) >= c * g(n)`. Big-Theta simply requires both bounds to hold for the same `g(n)`, so an algorithm only earns a Theta label when its upper and lower bounds genuinely match. With all three asymptotic notations in hand, you will be ready to switch focus to **Memory Models**, where the same growth-rate thinking gets applied to space rather than time.

Some problems have algorithms that finish in seconds on inputs of size a million. Others, like finding the shortest tour through 30 cities, can defeat the world's fastest computers no matter how cleverly you code. The boundary between these two worlds is studied formally in **complexity theory**, and the rough map of that boundary is given by **complexity classes**: `P`, `NP`, `NP-Complete`, and `NP-Hard`. This lesson introduces those classes conceptually. You will see how `P` collects problems solvable in polynomial time, how `NP` collects problems whose solutions can be *verified* in polynomial time (even if finding them might be slow), and how `NP-Complete` and `NP-Hard` capture the hardest problems in `NP` and beyond. You will meet famous examples (Traveling Salesman, SAT, the knapsack problem), get a light introduction to **polynomial-time reductions** as the tool used to prove a new problem is `NP-Complete`, and confront the legendary `P vs NP` question along with why it matters for cryptography and the entire structure of computer science. This lesson assumes you are fluent with all the basic asymptotic machinery from **Asymptotic Analysis Fundamentals**, **Big-O Notation (Upper Bound)**, **Time Complexity Analysis Techniques**, **Space Complexity Fundamentals**, and **Little-o and Little-omega Notations**. Complexity classes use those same growth-rate ideas to draw lines between "polynomial" and "exponential" rather than between specific functions like `n^2` and `n log n`. From here you will move into **Amortized Analysis**, shifting from broad problem classification back to the fine-grained per-operation analysis that complex data structures demand.

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**.

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.

Reading `arr[1000000]` takes the same amount of time as reading `arr[0]`, because an array's contiguous memory layout lets the runtime compute the address of any element with a single multiplication. That single property is what makes **Arrays & Strings** the workhorse data structure of nearly every program you will ever write. This lesson walks through array declaration and indexing in JavaScript and Python, the cost of inserts and deletes that force shifting, slicing and subarray patterns, and the basic string operations every interview problem assumes you know. You will also see why strings behave as immutable character arrays in both languages and what that means for performance when you build strings inside a loop. In **How to Read Code (JS & Python)**, you practiced tracing programs line by line; that habit is exactly how you will reason about loop indices and slice boundaries here. **Big-O Notation (Upper Bound)** gave you the language to express scaling behavior, and arrays are where you will first see `O(1)` access sit next to `O(n)` insertion in the same data structure. Once array fundamentals are second nature, **Matrix/Grid Fundamentals** extends the same indexing intuition into two dimensions, where row and column traversal patterns power BFS, DFS, and dynamic programming on grids.

An operating system rotating turns among four CPU-bound processes, a music player on shuffle-repeat, and the classic Josephus problem all share the same shape: a finite list of items consulted in cyclical order, where 'after the last' means 'back to the first'. A **Circular Linked List** encodes that shape directly, with the last node's `next` pointer wired to the head instead of `null`. This lesson covers the circular singly linked list and its doubly linked variant, the stop condition for traversal (return to the starting node rather than waiting for `null`), insertion at the head and at the tail in `O(1)` when a tail pointer is maintained, and deletion that correctly handles the wrap-around. You will also compare circular structures with the standard linear forms so you know when bending the list back on itself is the right call and when it just complicates traversal. In **Linked Lists (Singly)**, traversal terminated when you reached a `null` next pointer; here, the same loop must compare against the starting node instead, a small change that exposes the distinction between cycle detection and cycle definition (Floyd's tortoise-and-hare reuses this idea later). With all three linked-list shapes covered, the curriculum next pivots to tree-based and array-based structures with stronger time guarantees.

Deleting a node from a singly linked list when you only hold a pointer to that node is genuinely awkward: you need the previous node too, and finding it is `O(n)`. Add a `prev` pointer to every node and the same delete becomes four pointer rewires in `O(1)`, which is exactly the upgrade that powers LRU caches and the browser back-forward stack. This lesson covers the **Doubly Linked List** node layout (`value`, `next`, `prev`), bidirectional traversal, insertion at head and tail and after a given node, deletion by node reference and by value, and the sentinel (dummy head and tail) pattern that eliminates almost all null-check edge cases in pointer-heavy code. You will also weigh the per-node memory cost of the extra pointer against the operations it unlocks. In **Linked Lists (Singly)**, head insertion was already `O(1)` but mid-list deletion required carrying a trailing pointer during traversal. The doubly linked list removes that constraint: every node knows its predecessor, so you can splice it out without any extra bookkeeping. Next, **Circular Linked List** keeps a single direction of links but bends the list back on itself, which turns out to be the right shape for round-robin scheduling and circular buffers.

Two Sum is the canonical example: scan the array once, and for every number `x` ask the data structure whether you have already seen `target - x`. With a list that is `O(n^2)`. With a **Hash Map**, the lookup becomes a single function call and the whole algorithm collapses to `O(n)`. This lesson covers the key-value abstraction, the intuition behind a hash function (a key gets converted to a bucket index by an integer-valued function), what a collision is, and how `get`, `set`, `delete`, and `has` behave in JavaScript's `Map` and Python's `dict`. You will also meet two recurring patterns: counting frequencies and bucketing/grouping by a derived key, both of which appear in dozens of interview problems and real applications such as analytics, caching, and indexing. In **Arrays & Strings**, you saw that searching an unsorted array is `O(n)` because every position is equally plausible. A hash map turns that linear scan into an arithmetic computation that points directly at the right slot, which is the entire reason hash-based lookups dominate practical software. With key-based lookup in hand, **Set Basics** specializes the same machinery to a single question: have I seen this value before?

Inserting at the front of an array of one million items forces every existing element to slide one slot to the right. A **Linked List** sidesteps that copy entirely: a head insertion is two pointer assignments and nothing else, no matter how many nodes follow. In this lesson, each node holds a value and a `next` reference, and you chain those nodes into a singly linked list with explicit head and optional tail pointers. You will implement traversal, head and tail and middle insertion, deletion by value and by position, and linear search, and you will analyze each operation precisely so the trade-off against arrays becomes concrete: `O(1)` insertion at the head, `O(n)` access by index, and per-node memory overhead for the pointer. In **Arrays & Strings**, the `O(n)` cost of inserting near the front came from shifting; the linked list was invented to remove that shift. **Memory Models** introduced the difference between a contiguous block on the stack or heap and scattered allocations connected by references, and that mental model is exactly how a node-based structure lives in memory. Once you are comfortable manipulating `next` pointers, **Stack (LIFO)** uses a linked list (or a dynamic array) as its underlying storage and adds a strict push, pop, peek discipline on top.

Hold a fixed number of recently used items, evict the least-recently-touched one when you run out of room, and answer both `get(key)` and `put(key, value)` in `O(1)`. No single primitive does that: a hash map gives `O(1)` lookup but no recency order, and a doubly linked list gives `O(1)` recency moves but no key index. The classical **LRU Cache** wires the two together so each compensates for what the other lacks. This lesson designs the composite from scratch: a hash map that points keys to DLL nodes, and a doubly linked list that orders nodes by recency with most-recent at the head and least-recent at the tail. You will trace `get` and `put` through both structures, handle the capacity-of-one and update-existing-key edge cases, and see why this design appears in browser caches, database query caches, OS page replacement, and CDNs. In **Hash Map (Dictionary) Basics**, you used a hash map for `O(1)` lookup by key. **Doubly Linked List** added the `prev` pointer that makes mid-list deletion `O(1)` once you hold the node, plus the sentinel pattern that erases null checks at the boundaries; both are load-bearing here. The LRU pattern (one structure for indexing, another for ordering, kept consistent on every operation) is the gateway to a wider family of composite designs covered in later lessons.

Picture an image as a grid of pixels, a chessboard as an 8 by 8 array of squares, or a maze as a rectangle of walls and corridors. Each of these is a **Matrix/Grid**: a two-dimensional array indexed by `(row, column)` where the right traversal order can turn a hard problem into a single nested loop. This lesson covers how to allocate and initialize 2D arrays in JavaScript and Python, how row-major storage maps a `[i][j]` access to a contiguous memory offset, and the standard traversal patterns: row by row, column by column, and along the two diagonals. You will also practice boundary checks, the most common source of off-by-one bugs in grid problems, and implement a transpose to see how index swaps reshape data in place. In **Arrays & Strings**, you saw that a one-dimensional array gives `O(1)` indexed access through a single offset calculation. A grid is just nested arrays sharing that same property along two axes, so every shifting and bounds idea you used there carries over directly. Once you can move confidently through a grid, **Linked Lists (Singly)** shifts the focus to a very different memory layout: pointer-based nodes with no contiguous block at all.

Drop a million IDs into a `Set`, ask `set.has(id)` for any one of them, and the answer comes back in expected constant time without any ordering, sorting, or scanning. That single primitive (membership testing) is what makes a **Set** the quiet workhorse behind deduplication, visited-node tracking in graph traversal, and almost every cache-invalidation routine you will read. This lesson covers the uniqueness invariant of a set, the four core operations `add`, `delete`, `has`, and iteration in both JavaScript's `Set` and Python's `set`, and the four classical set-theory operations: union, intersection, difference, and symmetric difference. You will see why a set is implemented as a hash map whose values are unused, and you will practice the visited-set pattern that reappears in BFS, DFS, and cycle detection. In **Hash Map (Dictionary) Basics**, you learned that a hash function maps keys to bucket indices for `O(1)` get and set. A set keeps only the keys, drops the values, and exposes the resulting structure as a pure membership data type. Next, **Trees: Binary Tree Fundamentals** moves from flat unordered collections to hierarchical structures, where parent and child relationships unlock entirely new traversal patterns.

Searching a sorted array of one billion elements with linear search takes up to a billion comparisons. Binary search needs about thirty. The same input, the same hardware, two algorithms with completely different scaling behavior, separated only by the assumption that the array is sorted. **Binary Search (Intro)** explains how to get that speedup and how to write the algorithm without the off-by-one errors and infinite loops that trip up almost everyone the first time. You will implement the canonical two-pointer template with `left` and `right` indices, learn why `mid = left + (right - left) / 2` matters for avoiding integer overflow, and trace the algorithm step by step on small inputs to see the search space halve each iteration. The lesson also surveys built-in support across languages (`Array.indexOf` is _not_ a binary search; Python's `bisect` is) and the most common pitfalls. In **Arrays & Strings**, you saw why indexed access on an array is `O(1)`; binary search is the first algorithm that uses that property to skip past whole regions instead of walking through them. **Big-O Notation (Upper Bound)** gave you the language `O(log n)` and the reasoning that explains why halving leads to logarithmic growth. From here you will move into **Two Pointers (Intro)**, which generalizes the same coordinated-index idea beyond exact-match searching.

The mathematical definition `factorial(n) = n * factorial(n - 1)` defines a function in terms of itself, with `factorial(0) = 1` as the stopping point. That two-line definition is also a complete program if your language lets a function call itself. Recursion is what turns self-referential definitions into runnable code, and many problems (tree traversal, graph search, divide and conquer, dynamic programming) describe themselves most naturally that way. **Recursion Fundamentals** breaks down how that machinery actually works. You will learn to identify a base case (when the recursion stops) and a recursive case (how the problem reduces to a smaller instance), trace the call stack as frames are pushed and popped, and reason about return values flowing back up the chain. Examples run through factorial, naive Fibonacci, sum of an array, and integer power, plus a first look at recursion-tree intuition, tail recursion, stack overflow, and the `O(depth)` space cost of deep recursion. In **How to Read Code (JS & Python)**, you saw functions call other functions. **Debugging by Tracing** taught you to follow those calls step by step. Recursion is the case where the function on the call stack is the same function, again and again, with smaller inputs each time. Next, **Backtracking (Intro)** extends recursion with an explicit undo step to systematically explore combinatorial search spaces.

If your phone's contact list is unsorted and you are looking for Sam, the only option is to read names top to bottom until you find a match or hit the end. That brute-force scan is linear search, and it is the right algorithm in a surprising number of situations: small arrays, unsorted data, linked lists, and any case where sorting first would cost more than the search itself. **Searching (Basics)** covers linear search and its small family of variations. You will implement the standard `O(n)` scan in JavaScript and Python, learn the sentinel trick that removes a per-iteration boundary check, and adapt the same template to find the first occurrence, the last occurrence, or the first element matching a condition. The lesson also walks through linear search on linked lists, where you cannot skip ahead by index. In **Arrays & Strings**, you saw why arrays support `O(1)` random access. Searching turns that primitive into a question: how many of those accesses do you need to find a value, and can you do better than reading every one? That question motivates **Binary Search (Intro)** next, which exploits sorted order to bring the cost down to `O(log n)`.

To find the longest substring of `s` with no repeated characters, the brute-force approach checks every substring in `O(n^3)` time. The sliding-window solution touches each character at most twice and runs in `O(n)`: extend a right pointer until a duplicate appears, then advance a left pointer until the duplicate is gone, repeating until the right pointer falls off the end. **Sliding Window (Intro)** turns that idea into two reusable templates. The fixed-size window slides a range of length `k` across the array and updates the running sum or count by adding the new right element and removing the old left element, never recomputing from scratch. The variable-size window expands the right edge while a condition holds and shrinks the left edge to restore that condition, tracking the window's contents with a hash map or counter. You will apply both to maximum-sum subarray of size `k`, longest substring without repeating characters, minimum window substring, and longest substring with at most `k` distinct characters. In **Two Pointers (Intro)**, you used coordinated indices to walk an array linearly. **Hash Map (Dictionary) Basics** gave you the `O(1)` lookup and update that lets a window track its own contents efficiently. Sliding window combines both: two indices and one hash map. From here you turn to **Recursion Fundamentals**, which trades sequential index movement for self-similar subproblems.

Insertion sort is `O(n^2)` and quick sort is `O(n log n)`, yet V8 actually runs insertion sort on arrays shorter than ten elements because the constant factors are smaller. The takeaway is that elementary sorts are not just historical curiosities; they are the algorithms that real engines drop down to once an array is small enough. **Sorting (Elementary)** walks through bubble sort, selection sort, and insertion sort in detail. For each, you will trace the pass-by-pass behavior on a small input, count comparisons and swaps, and analyze worst, best, and average time complexity. Along the way the lesson introduces the vocabulary that every later sorting topic relies on: passes, the growing sorted region, the loop invariant that proves correctness, in-place vs. extra-space sorts, and stability (whether equal keys keep their original relative order). In **Arrays & Strings**, you learned how arrays store and index data; sorting is the first time you will rearrange that storage in place. **Iteration Patterns on Arrays/Strings** trained you in nested loops and swaps, and these three sorts are essentially structured nested loops with a clear invariant. Up next, **Searching (Basics)** establishes the linear-search baseline whose `O(n)` cost is exactly what binary search will later cut down once your data is sorted.

Given a sorted array and a target sum, the brute-force "check every pair" approach is `O(n^2)`. With two indices walking inward from opposite ends, the same problem drops to `O(n)`: if the current pair sums too low, move the left pointer right; if it sums too high, move the right pointer left. **Two Pointers (Intro)** turns that insight into a reusable pattern with two main shapes. The opposite-direction variant has pointers converge from both ends and powers problems like pair sum, palindrome check, reverse in place, and container with most water. The same-direction (fast and slow) variant has both pointers walk forward at different speeds and powers in-place filtering problems like remove duplicates from a sorted array, move zeros to the end, and the linked-list cycle detection you will revisit later. In **Arrays & Strings**, you learned how a single index walks across an array. This lesson coordinates two indices in a way that exploits sorted order or a structural invariant to skip work an inner loop would otherwise repeat. Next, **Sliding Window (Intro)** generalizes the same-direction pointer pair into an expanding and shrinking range that solves contiguous-subarray problems.