After this lesson, you will be able to: Read and reason about time and space complexity in Big O, analyze code to find its complexity, and compare O(1), O(log n), O(n), O(n log n), and O(n squared).
Big O notation is the foundation for everything else in this sub-track and the language interviewers expect you to speak. It describes how an algorithm's cost grows as the input grows. Get this right and every later lesson clicks into place.
This is a free introductory lesson. No purchase required.
Big O describes how the running time (or memory) of an algorithm grows as the input size n grows, ignoring constant factors and lower-order terms. It is about scaling, not stopwatch time. We care about the shape of the growth: does doubling the input double the work, square it, or barely change it? That shape is what determines whether your code survives at scale.
From fastest-growing to slowest. Memorize these shapes.
O(1) constant Array access, hash lookup. Input size does not matter.O(log n) logarithmic Binary search, balanced BST. Halves the problem each step.O(n) linear A single loop over the input.O(n log n) linearithmic Good sorts (merge, quick, heap). The bar for sorting.O(n^2) quadratic Nested loops over the same input. Avoid for large n.O(2^n) exponential Naive recursion (Fibonacci), subsets. Only tiny inputs.O(n!) factorial Permutations, brute-force traveling salesman.# For n = 1,000,000:# O(log n) ~ 20 steps# O(n) ~ 1,000,000 steps# O(n log n) ~ 20,000,000 steps# O(n^2) ~ 1,000,000,000,000 steps (will time out)
Count the loops and how the input shrinks.
# O(n): one loop proportional to nfor x in arr:print(x)# O(n^2): a loop inside a loop, both over nfor i in arr:for j in arr:print(i, j)# O(log n): the problem halves each iterationwhile n > 1:n = n // 2# O(n log n): an O(log n) or O(n) process repeated n times# (e.g., for each of n items, do a binary search)# Rules: drop constants (O(2n) -> O(n)); keep the dominant term# (O(n^2 + n) -> O(n^2)); sequential loops add, nested loops multiply.
Big O applies to memory too. Space complexity is how much extra memory an algorithm uses as a function of input size. A solution that builds a hash set of all n items uses O(n) space. An in-place algorithm that uses a few variables is O(1) space. Interviewers often ask for both time and space, and there is frequently a tradeoff: you can sometimes trade memory for speed (a hash map) or speed for memory (recomputing instead of caching).
Confusing O(n) with actual speed (a tight O(n squared) can beat a sloppy O(n) for small n, but n always wins eventually). Forgetting to drop constants and lower-order terms. Missing hidden loops (a string concatenation in a loop, or a .includes() inside a loop, can secretly be O(n squared)). Reporting only best case to look good. Ignoring space complexity entirely. Not recognizing that sorting inside a loop is often the hidden cost.