Definition
Why can a better method on an old laptop beat a worse method on a supercomputer?
Algorithm efficiency describes how the work an algorithm does grows as its input grows. Big-O notation gives that growth rate for the worst case, ignoring constant factors: O(1) is constant, O(log n) grows slowly, O(n) grows in step with the input, and O(n²) grows with the square of the input.
In simple words
Count steps, not seconds. Doubling the list doubles a linear search (O(n)) but adds just one step to binary search (O(log n)). Bubble sort on a list ten times longer takes about a hundred times as long (O(n²)). For big inputs, the growth rate matters far more than the speed of the computer.
Overview
- Efficiency describes how the time and memory an algorithm needs grow as the input size n grows.
- Big-O notation gives an upper bound on that growth, ignoring constant factors and small terms.
- It usually describes the worst case; best and average cases can also be stated.
- Time complexity counts steps; space complexity counts extra memory.
- Rules of thumb: a loop over n items is O(n); two nested loops are O(n²); halving each step is O(log n).
- The difference matters hugely for big data: n² is a trillion steps when n is a million.
Why it matters
AI works with millions of examples. An O(n²) step that is fine for 100 items can take days for a million. Big-O lets you predict this before running anything, and it is a standard topic in technical interviews.
Key terms
- Time complexity
- How the running time of an algorithm grows as the input grows.
- Space complexity
- How the memory an algorithm needs grows with the input.
- Big-O notation
- A way of writing the worst-case growth rate, ignoring constants, such as O(n).
- Input size n
- The quantity that grows, such as the number of items in a list.
- Worst case
- The input that makes the algorithm do the most work.
- Scalability
- Whether an approach still works when the data becomes very large.
Types
Algorithms fall into a small number of common growth classes. Here they are from fastest to slowest, with what each means in practice.
1. Constant time, O(1)
The work does not depend on the input size.
- How it works: The algorithm does a fixed number of steps, whether the list has 10 items or 10 million.
- Example: Reading marks[5], appending to a list, or looking up a key in a dictionary.
- When to use it: Aim for it in operations repeated millions of times; use dictionaries and sets to get it.
2. Logarithmic time, O(log n)
The work grows very slowly, adding one step each time the input doubles.
- How it works: The algorithm throws away a fixed fraction, usually half, of the remaining data at every step.
- Example: Binary search: about 20 steps for a million items and 30 for a billion.
- When to use it: Prefer it for searching large sorted data and for balanced tree structures.
3. Linear time, O(n)
The work grows in direct proportion to the input size.
- How it works: The algorithm looks at each item a fixed number of times, usually once.
- Example: Finding the maximum mark, summing a list or linear search.
- When to use it: Expect it for any task that must read all the data at least once; it is usually the best possible for such tasks.
4. Linearithmic time, O(n log n)
Slightly more than linear: n times the logarithm of n.
- How it works: Typical of divide-and-conquer algorithms that split the data log n times and do O(n) work at each level.
- Example: Merge sort and Timsort: sorting a million items takes about 20 million steps.
- When to use it: Accept it for sorting and similar tasks; it is the best possible for comparison-based sorting.
5. Quadratic time, O(n²)
The work grows with the square of the input size.
- How it works: Usually caused by two nested loops over the data, comparing every item with every other.
- Example: Bubble sort, or checking every pair of 10,000 students for duplicate phone numbers (about 50 million pairs).
- When to use it: Avoid it for large inputs; a set or sorting often turns it into O(n) or O(n log n).
6. Exponential time, O(2ⁿ)
The work doubles with every extra input item.
- How it works: Typical of trying every subset or every combination; 2⁵⁰ is over a thousand million million.
- Example: Brute-force knapsack with n items, or naive recursive Fibonacci.
- When to use it: Use it only for very small n; otherwise use dynamic programming, heuristics or genetic algorithms.
Explained in detail
Counting steps, not seconds
Timing a program with a stopwatch tells you how fast it ran on one computer with one input. Big-O notation answers a more useful question: how does the work grow as the input grows? It counts basic steps, keeps only the fastest-growing part and ignores constant factors. An algorithm that does 3n + 5 steps is O(n); one that does n² + 100n is O(n²), because for large n the n² term dominates. This lets you compare algorithms before writing them, and predict whether an approach will survive real data sizes.
The common classes
| Big-O | Name | Example | n = 1,000,000 |
|---|---|---|---|
| O(1) | Constant | Looking up a dictionary key | 1 step |
| O(log n) | Logarithmic | Binary search | About 20 steps |
| O(n) | Linear | Linear search, summing a list | 1,000,000 steps |
| O(n log n) | Linearithmic | Timsort, merge sort | About 20 million steps |
| O(n²) | Quadratic | Bubble sort, comparing every pair | 1,000,000,000,000 steps |
| O(2ⁿ) | Exponential | Trying every subset | Impossible |
At a billion simple steps per second, the O(n²) row takes about a quarter of an hour; the O(n log n) row takes a fiftieth of a second. That gap, not the speed of your computer, decides what is practical.
Reading complexity from code
- A single loop over n items is usually O(n).
- A loop inside a loop, both over n, is usually O(n²).
- Halving the problem each step gives O(log n).
- Hidden loops count: x in a_list inside a loop makes O(n²), while x in a_set keeps it O(n).
- Python's built-ins have known costs: list.append is O(1), list.insert(0, x) is O(n), sorted is O(n log n).
Why this matters for AI
AI works with huge data, so complexity decides what is possible. Comparing every pair of a million images is out of reach, which is why search engines and recommendation systems use special indexes. The attention mechanism in transformers is O(n²) in the length of the text, which is the main reason language models have context limits and why researchers work hard on cheaper alternatives. Knowing Big-O lets you understand these limits instead of being puzzled by them.
Big-O describes growth, not exact speed. For small inputs a simple O(n²) method can beat a clever O(n log n) one, so measure when it matters.
How it works
| Big-O | Name | Example | Steps for n = 1,000 |
|---|---|---|---|
| O(1) | Constant | Look up a list item by index | 1 |
| O(log n) | Logarithmic | Binary search | ≈ 10 |
| O(n) | Linear | Linear search, summing a list | 1,000 |
| O(n log n) | Linearithmic | sorted() | ≈ 10,000 |
| O(n²) | Quadratic | Bubble sort, comparing every pair | 1,000,000 |
The maths
- The number of items in the sorted list
- How many times n can be halved before reaching 1
In code
Counting the worst-case work of three algorithms as the input grows.
import math
def linear_checks(n):
return n # look at every item
def binary_checks(n):
return math.floor(math.log2(n)) + 1
def bubble_comparisons(n):
return n * (n - 1) // 2 # every pair, roughly
print(f"{'n':>9} {'linear':>9} {'binary':>7} {'bubble':>15}")
for n in [10, 100, 1000, 1000000]:
print(f"{n:>9} {linear_checks(n):>9} {binary_checks(n):>7} {bubble_comparisons(n):>15}")Output
n linear binary bubble
10 10 4 45
100 100 7 4950
1000 1000 10 499500
1000000 1000000 20 499999500000Try it yourself
Which grows fastest?
Put each task under its Big-O growth rate.
Check every pair of students for a shared birthday
Add up all the numbers in a list
Find a name in a sorted phone book by halving
Get the first item of a list
Find the largest mark in an unsorted list
Common mistakes
- Timing on tiny inputs and concluding that the method doesn't matter.
- Thinking O(n) means exactly n steps. It describes how work grows, ignoring constants.
- Forgetting that sorting first costs O(n log n).
Check yourself
Summary
- Efficiency is how work grows with input size.
- Big-O: O(1) < O(log n) < O(n) < O(n log n) < O(n²).
- For big data, choose the algorithm before buying a faster computer.
Finished reading?
Sources: W3Schools DSA: Time Complexity