Algorithmic Complexity and Data Structures
Problem
Your application finds a customer by checking every record in a list. With 1,000 customers, this feels instant. With ten million customers and hundreds of searches per second, the same approach becomes expensive. Why does adding data change performance so much?
Solution — Algorithmic Complexity
An algorithm is a procedure for solving a problem. A data structure is how the data is organized. Together, they determine how much work an operation needs.
The letter n means the number of input items. For a list of 1,000 customers, n is 1,000. Big O describes a bound on how the amount of work grows as n increases. The examples below count checks or comparisons so you can see the different growth patterns.
1. O(n): work grows with the number of items
Imagine an unsorted customer list. To find customer 87, you check the first entry, then the second, and keep going until you find a match.
If the customer is last or missing, you inspect every entry. This worst case needs up to n checks:
1,000 customers → up to 1,000 checks 10,000 customers → up to 10,000 checks
Ten times as many customers can mean ten times as much work. This is called linear growth. A match near the beginning can still be found quickly.
2. O(log n): repeatedly cut the search area in half
Now imagine an array sorted by customer ID. Binary search checks the middle entry. If the requested ID is smaller, continue in the lower half; if it is larger, continue in the upper half. Repeat until you find the ID or the remaining range is empty.
Each check removes roughly half the remaining candidates. This works because the IDs are sorted and an array lets you access its middle directly.
1,000 customers → at most about 10 checks 1,000,000 customers → at most about 20 checks
The list became 1,000 times larger, but the number of checks only roughly doubled. The logarithm here counts the repeated halvings; you do not need to calculate it by hand. Doubling the input adds roughly one more check.
3. Expected O(1): average work stays roughly constant
Imagine a hash table that maps customer IDs to customer records. When inserting a record, the table uses a hash function to determine where to place it. Later, the same function helps locate the entry for that ID.
For a well-managed table and fixed-size IDs, a lookup examines a small number of candidate entries on average, rather than walking through the whole collection.
1,000 customers → roughly constant average lookup work 1,000,000 customers → roughly constant average lookup work
The 1 means the expected work stays bounded as the collection grows. It does not mean exactly one CPU instruction. “Expected” describes an average under the table's hashing assumptions, rather than a promise about every individual lookup. These figures describe looking up an entry after the table has been built.
4. O(n²): items are compared with other items
Imagine checking every pair of customer records for a possible duplicate. Each record has to be compared with all the other records, with each pair checked once.
With three records, A, B, and C, the pairs are A–B, A–C, and B–C. As records are added, the number of pairs grows quickly:
10 records → 45 distinct pairs 100 records → 4,950 distinct pairs 200 records → 19,900 distinct pairs
Going from 100 to 200 records roughly quadruples the comparisons. This is quadratic growth: the work grows in proportion to the square of n. The exact number of distinct pairs is n × (n − 1) ÷ 2; Big O summarizes that growth as O(n²).
Core idea: O(n) grows with the list, O(log n) grows through repeated halvings, expected O(1) stays roughly constant on average, and O(n²) grows with the number of pairs.