We already know what an algorithm is and what types exist; now we need a rigorous language to answer the key question of the course: which of these two algorithms is more efficient? That language is asymptotic notation: a way of describing how an algorithm's cost grows as its input size grows, independent of the computer, the language, and the stopwatch. Mastering it is essential: we will use it in every remaining lesson of the course, it appears in all serious technical documentation (have you seen "O(1) average" in the documentation for Python dictionaries?), and it is a fixture in technical interviews.

1. Why measure growth rather than wall-clock time
2. The central idea: how cost scales with n
3. Big O, Ω, and Θ: what each one means
4. The hierarchy of common orders with the RutaBus network
5. Practical simplification rules
6. What comes next: Module 2

The first temptation when comparing algorithms is to time them. Let's run the thought experiment with RutaBus: two developers implement the search for a stop by name and measure the time with 10,000 stops.

Is A's algorithm better? We cannot tell from these figures. Wall-clock time mixes in too many things that have nothing to do with the algorithm:

• The hardware: CPU, cache memory, disk... The same linear search can be 50 times faster on one machine than on another.
• The language and its implementation: interpreted Python vs compiled C; even different versions of Python.
• The state of the system: other processes, the operating system, luck.
• The chosen input size: with 10 stops almost any algorithm looks instantaneous; the differences explode as the data grows.

What is a property of the algorithm (and not of the machine) is how many basic operations it needs as a function of the input size, n. If we repeat the experiment varying n (the number of stops), the picture changes:

A's fast machine gives her an edge for small n, but no machine can compensate for a difference in growth: at a million stops, B's algorithm does 50,000 times less work. Asymptotic notation captures exactly this: the growth rate of the cost as n gets large, ignoring constant factors that depend on the machine.

We call n the size of the input (the number of stops in the network, the number of timetable entries to sort...) and f(n) the number of basic operations the algorithm performs for that input. The asymptotic question is: when n doubles, what happens to f(n)?

• If f(n) = 3n + 5, doubling n roughly doubles the cost: linear growth.
• If f(n) = n², doubling n multiplies the cost by 4: quadratic growth.
• If f(n) = 20 (independent of n), the cost doesn't change: constant growth.

Notice that the "3" and the "+5" in the first function barely matter for this question: 3n + 5 and 900n + 2000 behave the same qualitatively (doubling n ≈ doubling cost), even though one is 300 times slower than the other. That factor of 300 is what the machine, the language, etc. absorb; the type of growth is not. That is why asymptotic notation discards constants and keeps only the shape of the curve.

The three notations express bounds on the growth of f(n). Here is the semi-formal definition and, above all, the practical meaning of each:

We say that f(n) is O(g(n)) if, beyond a certain input size, f(n) stays below g(n) multiplied by some constant. Formally: there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.

Practical translation: "the algorithm's cost grows no faster than g(n)". It is an upward guarantee: that is why it is the most widely used notation, since as engineers we care about bounding the worst possible behavior.

Example: the linear search for a stop makes at most n comparisons → it is O(n). Technical note: it would also be formally correct to say it is O(n²) (a looser upper bound), but by convention we always give the tightest bound known.

We say that f(n) is Ω(g(n)) if, beyond a certain n, f(n) stays above c·g(n) for some constant c > 0.

Practical translation: "the cost cannot be lower than that order". It is used to express limits on what is possible. Example: any algorithm that must display all the stops in the network is Ω(n) — there is no way to list n things in fewer than n steps.

We say that f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)): the cost is trapped between two multiples of g(n).

Practical translation: "the cost grows exactly at the rate of g(n)". It is the most informative characterization when it can be given. Example: counting the stops in a list by traversing it entirely is Θ(n): exactly one step per stop, no more and no less.

One nuance worth noting down: these notations describe the growth of a cost function, and the same algorithm may have different cost functions depending on whether the input is favorable or not (linear search finds "Main Square" on the first try if it happens to be at the front of the list...). That analysis by best, worst, and average case has its own lesson (02-03); for now, when we say an algorithm "is O(n)" we will mean its worst-case behavior, which is the most common use of Big O.

These are the growth orders you will run into again and again, from best to worst:

The names come alive with concrete numbers. Suppose each operation costs 1 microsecond (one millionth of a second) and let n be the number of stops in the RutaBus network:

Key takeaways from this table:

• O(log n) is almost as good as O(1): going from 10 to 100,000 stops only multiplies the cost by ~6. Doubling n adds one operation. That is why binary search is so valuable.
• O(n log n) scales very well: sorting 100,000 timetable entries takes under 2 seconds. It is the order of the good sorting algorithms.
• O(n²) becomes unworkable surprisingly early: with a large city's network (100,000 stops), computing all pairwise distances would take hours. A quadratic algorithm that "ran fine in testing" with 100 stops can sink the application in production.
• O(2ⁿ) is intractable except for tiny n: with just 100 elements, the universe has not existed long enough to finish the computation. When a problem only admits exact exponential solutions, the heuristics we saw in the previous lesson come into play.

As a quick reference in Python (the exact reason behind each cost is analyzed in Module 2):

When expressing an algorithm's cost, asymptotic notation is simplified with two mechanical rules:

Constant factors depend on the machine and the language, not on the algorithm, so they are dropped:

• 5n → O(n)
• n/2 → O(n) (dividing by 2 is multiplying by the constant 0.5)
• 300 → O(1) (any fixed cost, however large, is constant)

Careful: this does not mean constants don't matter in real life. Between two O(n) algorithms, the one with the smaller constant wins; the notation only says that this nuance doesn't change the shape of the growth. We will revisit this tension in Module 5 (optimization).

When the cost is a sum of terms, for large n one of them "swallows" the rest — the one that grows fastest according to the hierarchy we just saw:

• n² + 10n + 500 → O(n²)
• n log n + n → O(n log n)
• 2ⁿ + n³ → O(2ⁿ)

Why is this legitimate? Check it with numbers: for n = 10,000, n² = 100,000,000 while 10n + 500 = 100,500 — less than 0.1% of the total. The larger n gets, the more irrelevant the smaller term becomes.

A RutaBus function does the following with a network of n stops:

1. Reads the app's configuration → fixed cost: 25 operations.
2. Sorts the stops alphabetically → n log n operations.
3. Traverses the sorted list to flag the accessible ones → n operations.
4. Checks the user's 2 favorite stops → 2 operations.

Total cost: f(n) = n log n + n + 27. Applying the rules: we discard the constants (27) and keep the dominant term (n log n swallows n). Result: O(n log n).

Quick practice table:

With asymptotic notation we now know how to express an algorithm's efficiency. What we haven't done yet is derive it from code: look at a Python function line by line, count its operations and loops, and conclude "this is O(n²)". That is exactly the goal of the next lesson (02-01, time complexity). Module 2 then completes the picture with space complexity (how much memory an algorithm consumes, 02-02) and the analysis of best, worst, and average cases (02-03), which we have only hinted at here.

• Comparing algorithms by timing them on a single machine with a single input size. Benchmarking has its place (Module 5), but the conclusion "A is better than B" is only solid if you compare growth rates. Tip: if you measure, measure with several increasing n values (n, 2n, 4n...) and observe how each one scales.
• Believing Big O describes the exact time. O(n) does not say "it takes n seconds" nor "it performs exactly n operations"; it says the cost grows at most linearly. Two O(n) algorithms can differ by a factor of 100.
• Ignoring constants when n is small. For n = 20, a simple O(n²) can beat a sophisticated O(n log n). Asymptotics rules when n grows; with tiny data, measure.
• Using O, Ω, and Θ interchangeably. Saying "this algorithm is Ω(n²)" claims it costs at least n² — you probably meant O(n²) (at most) or Θ(n²) (exactly). Check which bound you intend to express.
• Adding when you should keep the dominant term... or the other way around. Sequential steps add up and then the largest dominates: O(n) followed by O(n log n) is O(n log n), not O(n · n log n). Multiplication appears with nested loops, which we will analyze in 02-01.
• Thinking "asymptotic" means irrelevant theory. The growth tables show the opposite: the difference between O(n²) and O(n log n) is the difference between an app that responds instantly and one that freezes when the city adds stops.

Simplify each of these cost functions to its asymptotic order (Big O), stating which rule you apply:

a) f(n) = 4n + 90 b) f(n) = n²/10 + 50n + 3 c) f(n) = 1000 d) f(n) = 2n log n + n² + 7n e) f(n) = log n + 25

The RutaBus network is going to grow from 1,000 to 100,000 stops (a factor of 100). For each of these three algorithms, work out (approximately) by how much its number of operations will multiply, and decide which ones will remain viable if today they take 1 ms with 1,000 stops:

a) Algorithm X: O(n) b) Algorithm Y: O(n²) c) Algorithm Z: O(log n) — use log₂(1,000) ≈ 10 and log₂(100,000) ≈ 17

State whether each claim is true or false and justify your answer:

a) An O(n²) algorithm always takes longer than an O(n) one, for any input. b) If an algorithm is Θ(n), then it is also O(n) and Ω(n). c) Displaying the network's n stops on screen can be done in O(log n). d) f(n) = 5n + 20 is O(n²).

Solution 1:

a) O(n) — rule 1: the multiplicative constant 4 and the additive 90 are discarded. b) O(n²) — rule 2: n² dominates 50n; rule 1: the 1/10 and the 3 are discarded. c) O(1) — a fixed cost, however large, is constant. d) O(n²) — rule 2: in the hierarchy, n² grows faster than n log n, so it dominates. e) O(log n) — the constant 25 is discarded; the logarithmic term remains.

Solution 2:

a) X (O(n)): the cost scales linearly → ×100. From 1 ms it would go to ~100 ms. Viable, though starting to be noticeable. b) Y (O(n²)): the cost scales with the square → ×100² = ×10,000. From 1 ms it would go to ~10 seconds. Not viable for an interactive app operation. c) Z (O(log n)): the cost goes from ~10 to ~17 units → ×1.7. From 1 ms it would go to ~1.7 ms. Perfectly viable: this is the magic of logarithmic growth.

Solution 3:

a) False. The notation describes growth for large n, not the time for every input: with small n, the constants can let the O(n²) algorithm win (e.g., 2n² versus 1000n for n < 500). What is true: beyond some n, the O(n) one always ends up winning. b) True. That is the definition of Θ: a tight bound means being simultaneously an upper bound (O) and a lower bound (Ω) of the same order. c) False. Producing n lines of output requires at least n operations: the problem is Ω(n), and no algorithmic cleverness can go below that. d) True, but misleading. Formally 5n + 20 ≤ n² beyond a certain n, so the claim satisfies the definition of O. However, the tight bound is O(n) — and by convention the tightest known bound is always given. This nuance (that O is only an upper bound) is the source of the mistake of using it as if it were Θ.

In this lesson we acquired the language in which efficiency is discussed in computer science. We saw why wall-clock time is useless for comparing algorithms (it measures the machine as much as the method) and why the cost's growth rate with respect to input size works instead. We defined the three notations —Big O as an upper bound, Ω as a lower bound, and Θ as a tight bound—, walked through the hierarchy of common orders from O(1) to O(2ⁿ) verifying with the RutaBus stop network that the difference between them is not academic but brutal, and practiced the two simplification rules: discard constants and keep the dominant term. With this language in hand, in Module 2 we will learn to calculate the complexity of a real algorithm: we will analyze Python code line by line to derive its time complexity (02-01), we will also measure its memory consumption (02-02), and we will distinguish its behavior in the best, worst, and average cases (02-03) — starting, of course, with the algorithms we have already written for RutaBus.