Welcome to the first module of Advanced Algorithms. Before we optimize anything, we need a common language for talking about algorithms: what they are exactly, what it means for one to be "better" than another, and how to express their cost precisely and independently of the machine they run on. In this lesson we build that language: the properties of an algorithm, the RAM model of computation, asymptotic notation (O, Ω, Θ), and pseudocode as a communication tool.

To give the whole course a running context, we will work with Rutalia, a fictional urban last-mile logistics company. Rutalia manages orders, schedules delivery rounds, and looks up addresses thousands of times a day. When it handled 100 orders a day, any reasonable program worked fine. Now it processes close to a million, and suddenly some operations take hours. Understanding why that happens — and anticipating it before writing any code — is the goal of this lesson.

1. What an algorithm is and what properties it must satisfy
2. Correctness versus efficiency
3. The RAM model of computation
4. Asymptotic notation: O, Ω, and Θ
5. The hierarchy of growth rates
6. Pseudocode and its Python equivalents

An algorithm is a well-defined computational procedure that takes one or more values as input and produces one or more values as output, through a finite sequence of precise steps.

For a procedure to deserve the name "algorithm" it must satisfy these properties:

• Finiteness: it terminates after a finite number of steps. A process that may never finish is not a valid algorithm.
• Precise definition (no ambiguity): every step is specified unambiguously. "Pick a reasonable order" is not a valid step; "pick the order with the earliest delivery deadline" is.
• Input: zero or more values supplied before it starts (for example, the day's list of orders).
• Output: one or more values related to the input (for example, the list of orders sorted by deadline).
• Effectiveness: every operation is basic enough to be carried out mechanically in finite time.

At Rutalia, "sort van 7's deliveries by delivery deadline" is a problem; the concrete procedure that solves it (say, a sorting algorithm) is the algorithm; and the Python code that implements it is the program. Keeping the three levels apart matters: a single problem admits many algorithms, and a single algorithm admits many implementations.

An algorithm is judged along two independent dimensions:

Two key ideas:

• Correctness is non-negotiable. A blazingly fast algorithm that occasionally loses orders is useless. Correctness is argued by reasoning about the algorithm (base cases, loop invariants), not just by trying examples: tests can show the presence of bugs, but never their absence.
• Efficiency is measured as a function of the input size, which we will usually call n. We do not care about "how many milliseconds it takes on my laptop" — we care about how the cost grows as n grows. That growth is what decides whether Rutalia's system survives the jump from 100 orders to 1,000,000.

An illustrative example. Suppose we have two correct algorithms for looking up an address among n registered addresses:

• Algorithm A performs on the order of n operations.
• Algorithm B performs on the order of log₂ n operations (it requires sorted data).

With n = 100, A does ~100 operations and B ~7: the difference is irrelevant. With n = 1,000,000, A does a million operations and B ~20. If that lookup runs once for every incoming order, the difference stops being academic: it is the difference between a relaxed server and a saturated one. In lesson 01-02 we will learn to calculate these costs; here it is enough to know how to express them.

To count operations we need to agree on what counts as "one operation". The standard model is the RAM machine (Random Access Machine), an idealization of a real computer with these rules:

• There is a memory made of cells, and accessing any cell costs the same (constant time), regardless of its position. Hence "random access".
• Elementary operations cost one unit of time each: basic arithmetic (+, -, *, /, modulo), comparisons (<, ==), assignments, reads/writes of a single cell, and control transfers (if, call, return).
• Instructions execute one after another, with no parallelism.
• Each cell stores a number of reasonable size (no cheating by stuffing an entire file into "one cell").

It is a deliberate simplification: it ignores caches, pipelines, and the details of real hardware. In exchange, it gives us something invaluable: analyses performed on the RAM model predict the relative behavior of algorithms on any real machine. If in the RAM model algorithm B grows much more slowly than algorithm A, it will do so in production too (beyond a certain input size).

A practical caution with Python: some operations that fit on one line are not elementary. For example:

Each of these lines hides a cost proportional to n. When analyzing Python code you have to mentally "translate" each construct into the number of RAM operations it implies.

Counting exact operations is tedious and not very useful: does it really matter whether it is 3n + 7 or 5n + 2 operations? What matters is that both grow linearly. Asymptotic notation captures exactly that: the behavior of the cost as n gets large, ignoring multiplicative constants and lower-order terms.

Formal definition: f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀.

Intuition: beyond a certain size, f never grows faster than g (up to a constant). It is a promise of the form "at worst, this bad". Example: 3n + 7 = O(n) (take c = 4 and n₀ = 7, because 3n + 7 ≤ 4n when n ≥ 7). It is also true that 3n + 7 = O(n²) — an upper bound does not have to be tight — although by convention we state the tightest bound we know how to prove.

Formal definition: f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that f(n) ≥ c · g(n) for all n ≥ n₀.

Intuition: beyond a certain size, f grows at least as fast as g. It is the opposite promise: "at the very least, this much". Example: any algorithm that must look at every order at least once is Ω(n): no possible implementation can go below that.

Formal definition: f(n) = Θ(g(n)) if f(n) = O(g(n)) and at the same time f(n) = Ω(g(n)).

Intuition: f and g grow at the same rate, up to constants. It is the exact characterization of the growth rate. Example: 3n + 7 = Θ(n).

Practical simplification rules:

• Multiplicative constants are dropped: 500n = O(n).
• The largest term dominates: n² + 1000n + 3 = Θ(n²), because for large n the n² term dwarfs the others.
• Logarithm bases do not matter: log₂ n and log₁₀ n differ by a constant factor, so both are Θ(log n).

A common subtlety: in professional practice almost everyone says "this algorithm is O(n log n)" when they mean Θ(n log n). It is a tolerated abuse of language; in this course we will use Θ when we assert the exact order and O when we only bound from above.

An important note: O, Ω, and Θ describe cost functions, not "worst case / best case". You can give an O bound on the best case or an Ω bound on the worst case. The relationship between cases (best, worst, average) and these notations is covered carefully in lesson 01-02.

The usual growth rates, from slowest to fastest growing:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

To make them tangible, suppose a machine that executes 10⁸ elementary operations per second (a modest computer) and look at how long each growth rate would take with Rutalia's volumes:

Three takeaways from this table worth internalizing:

• With small n, everything works. With 100 orders, even the quadratic algorithm responds in a tenth of a millisecond. That is why performance problems show up later, once the business grows. Rutalia's code did not "break": n simply changed scale.
• The jump from O(n log n) to O(n²) is the most common practical cliff. Sorting a million deliveries: 0.2 seconds. Naively comparing every order against every other to detect duplicates: almost 3 hours. Same hardware, same language.
• Exponential and factorial orders cannot be fixed with hardware. If an O(2ⁿ) algorithm is infeasible for n = 100, buying a machine 1000 times faster only gets you to n ≈ 110. Against exponential growth, the only weapon is a better algorithm (or accepting approximate solutions, as we will see in module 2).

Pseudocode is a description of an algorithm halfway between natural language and a programming language: precise enough to be unambiguous, abstract enough not to get distracted by syntax. It is the language algorithm textbooks are written in, and the one it pays to think in before coding.

Common conventions and their direct translation to Python:

A complete example. Pseudocode for finding the order with the earliest deadline (the most urgent one) in a van:

And its literal translation to Python:

Notice how each line of pseudocode corresponds to a Python construct, and how the comments already point toward operation counting (how many times each line runs). The loop visits each order exactly once, so the cost is proportional to n: this algorithm is Θ(n). The systematic analysis of this kind of code — including nested and dependent loops and best/worst/average cases — is the subject of the next lesson.

Tips for writing good pseudocode:

• Name variables after their meaning (deadline, not x).
• Make preconditions explicit (can the list be empty?).
• Leave out irrelevant language details (exception handling, exact types), but keep everything that affects correctness or cost.
• If a step hides non-constant work ("look up d in the list"), be aware of it: when analyzing, that step does not cost 1.

• Confusing O with "worst case". O is an upper bound on a function; it can be applied to the worst case, the best case, or the average case. Saying "the best case of this algorithm is O(n)" is perfectly legitimate.
• Believing that O(1) means "fast". It means "cost that does not depend on n". An O(1) operation can take a fixed 10 seconds; an O(n) one with a tiny constant can beat it for all realistic n. Asymptotic notation compares growth, not absolute times.
• Ignoring constants when n is small. For lists of 20 orders, a simple O(n²) algorithm may in practice be faster than a sophisticated O(n log n) one. Asymptotics rule when n grows; common sense rules always.
• Forgetting the hidden cost of Python operations. x in some_list, some_list.insert(0, x), some_list[:], or a slice all cost O(n), even though they fit on one line. It is the number one mistake when analyzing Python code.
• Writing ambiguous pseudocode. If two people can interpret a step differently, it is not pseudocode: it is prose. Rewrite it until it admits only one reading.
• Tip: when in doubt about the growth rate, ask yourself what happens if n is multiplied by 10. Does the cost multiply by 10 (linear), by 100 (quadratic), or barely change (logarithmic)? This mental test resolves most doubts.

Simplify each cost function to its Θ notation and sort them from slowest to fastest growth:

1. f₁(n) = 4n² + 100n + 7
2. f₂(n) = 50·n·log n + 3n
3. f₃(n) = 2ⁿ + n¹⁰
4. f₄(n) = 1000 (constant)
5. f₅(n) = 7n + 12·log n

Rutalia's duplicate-order detection system executes exactly n²/2 elementary operations for n orders, on a machine performing 10⁸ operations per second.

1. How long does it take with n = 1,000, n = 100,000, and n = 1,000,000?
2. An engineer proposes an alternative algorithm of 20 · n · log₂ n operations. How long would it take with n = 1,000,000? At roughly what scale does the switch start to pay off?

Translate the following pseudocode into Python — it checks whether any order in the van exceeds the maximum allowed weight — and give a reasoned account of its growth rate in the worst case and in the best case.

Solution 1

1. f₁ = Θ(n²) — 4n² dominates; the constant and the smaller terms are dropped.
2. f₂ = Θ(n log n) — n log n dominates n.
3. f₃ = Θ(2ⁿ) — any exponential dominates any polynomial, even n¹⁰.
4. f₄ = Θ(1) — it does not depend on n.
5. f₅ = Θ(n) — n dominates log n.

From slowest to fastest growth: f₄ (Θ(1)) < f₅ (Θ(n)) < f₂ (Θ(n log n)) < f₁ (Θ(n²)) < f₃ (Θ(2ⁿ)).

Solution 2

1. With n = 1,000: 10⁶/2 = 5·10⁵ operations → 0.005 s. With n = 100,000: 10¹⁰/2 = 5·10⁹ → 50 s. With n = 1,000,000: 10¹²/2 = 5·10¹¹ → 5,000 s ≈ 83 minutes. Notice the quadratic pattern: multiplying n by 10 multiplies the time by 100.
2. With n = 1,000,000: log₂(10⁶) ≈ 20, so 20 · 10⁶ · 20 = 4·10⁸ operations → 4 seconds. Setting n²/2 = 20·n·log₂ n gives n = 40·log₂ n, which holds around n ≈ 350. In other words: below roughly ~350 orders the quadratic algorithm (with its small constant) is competitive; at Rutalia's current scale, the switch is indispensable. Moral: constants decide for small n; the growth rate decides for large n.

Solution 3

• Worst case: no order exceeds the maximum (or only the last one does). The loop scans all n orders → Θ(n).
• Best case: the very first order already exceeds the maximum. A single comparison is made → Θ(1).

Notice how one and the same algorithm has different cost functions depending on the case; formalizing this distinction is part of the next lesson. Common mistakes here: forgetting the final return False (the function would return None), or accumulating results in a list instead of exiting as soon as the first one is found (which would lose the Θ(1) best case).

In this lesson we built the fundamental vocabulary of the course. An algorithm is a finite, precise, effective procedure that transforms inputs into outputs; it is judged first by its correctness and then by its efficiency. To measure efficiency independently of the machine we use the RAM model (every elementary operation costs 1) and asymptotic notation: O bounds from above, Ω from below, and Θ characterizes the exact growth. The hierarchy of growth rates — from O(1) to O(n!) — explains why Rutalia's software worked with 100 orders and chokes with a million: it is not a hardware issue, it is a growth issue. Finally, pseudocode gives us a precise language for designing before coding, with a direct translation to Python.

We now know how to express costs; the next step is to calculate them. In the next lesson, Complexity Analysis, we will learn the systematic techniques for determining an algorithm's time and space complexity: operation counting, nested and dependent loops, case analysis (best, worst, average), amortized analysis, and a first look at recurrences. We will analyze real functions from Rutalia's codebase and discover, with actual numbers, where that hours-long process is hiding.