Time Complexity and Space Complexity of an Algorithm Explained
Picture two programs that do the exact same job. Feed each one a thousand records and you can't tell them apart. Feed them a billion, though, and one finishes before you've let go of the Enter key while the other is still grinding away next Tuesday.
Same laptop. Same data. What separates them is time complexity, which is just a name for how fast an algorithm's workload balloons as you hand it more input.
We'll go through what the term actually means, how Big O notation writes it down, how to work it out from a real piece of code, and where space complexity comes in. Then, at the end, a place where all of this stops being homework and starts costing actual money: smart contracts.
What Is Time Complexity of an Algorithm?
Forget seconds for a moment. Time complexity counts steps. Comparisons, assignments, a bit of arithmetic here and there, and you write the total as a function of n, which is the input size.
Here's about the most boring function imaginable:
python def print_all(items): for item in items: print(item)
Ten items? Ten trips through the loop. Ten thousand? Ten thousand trips.
The work climbs in a straight line next to the input, so we call it O(n).
Now, maybe each trip really costs three little operations instead of one. Fine, that's 3n. Nobody cares, honestly, because doubling the list still doubles the work, and that growth curve is the bit we want. The exact number gets thrown out on purpose.
That's also why every DSA course and half the coding interviews out there hammer on time complexity. If you can read off the complexity of an algorithm by looking at it, you can guess how it'll behave on input data you never got around to testing. Which, in production, is most of the data.
Why Execution Time Is a Poor Measure of an Algorithm
So why not just run the thing with a timer? Plenty of people do, and I get it. The catch is that execution time drags in a pile of stuff your algorithm has nothing to do with:
- Hardware. My five-year-old laptop and a brand-new cloud box will give you wildly different numbers for the same script.
- Programming language. Write the same loop in C and in Python and you might see a 10× gap, or more.
- System load. Some background updater kicks in, the garbage collector wakes up, the cache is cold. Your result moves.
- Whatever input you happened to grab. A sort that flies on almost-sorted data can crawl on shuffled data.
A stopwatch gives you one run on one box with one input. Ask it about 100× the data and it's got nothing.
Step counts don't wobble. Same algorithm, same input, and you get the same number of steps whether it's Rust on a rack server or JavaScript on somebody's phone. That's why time complexity is a fair fight between two solutions before you've benchmarked a thing. I'd still benchmark afterwards, for what it's worth. It's just a different question.
Big O and Other Asymptotic Notations Explained
Textbooks call this asymptotic notation, which sounds worse than it is. You let n get enormous and stop caring about the small stuff, so constant multipliers and tiny inputs drop out and only the growth curve survives. There are three of them worth knowing:
| Notation | What it describes | Plain meaning | Example |
|---|---|---|---|
| Big O, O(f(n)) | Upper bound | The algorithm grows no faster than f(n) | Linear search is O(n) |
| Big-Omega, Ω(f(n)) | Lower bound | The algorithm needs at least f(n) work | Any comparison sort is Ω(n log n) |
| Big-Theta, Θ(f(n)) | Tight bound | Upper and lower bounds match | Merge sort is Θ(n log n) |
In practice you'll hear Big O notation about 95% of the time. It sets an upper bound, meaning the running time won't grow faster than the rate inside the parentheses. My first code review at a real job had a senior dev write "O(n²), pls fix" next to a nested loop, and what they meant was that the worst-case time complexity was quadratic and the list was about to get a lot longer.
Omega and Theta mostly live in university courses on the analysis of algorithms, and I don't think I've typed either one at work in years. Big O wins out because it answers what people actually ask in a meeting, which is "how bad does this get if traffic triples?"
There's one technicality that confused me for a while. Since Big O is only a ceiling, an O(n) function is also O(n²), strictly speaking, the same way a 5-foot person is "under 7 feet." True and useless. Everybody quotes the tightest bound they can justify and I'll do the same.
Common Time Complexity Classes With Examples
There aren't that many classes you'll see in real code, maybe seven if you count the scary ones. This is roughly what each costs at n = 1,000:
| Class | Name | Typical example | Operations at n = 1,000 |
|---|---|---|---|
| O(1) | Constant | Array index, hash table lookup | 1 |
| O(log n) | Logarithmic | Binary search | ~10 |
| O(n) | Linear | Scanning a list | 1,000 |
| O(n log n) | Linearithmic | Merge sort, quicksort (average) | ~10,000 |
| O(n²) | Quadratic | Nested loops, bubble sort | 1,000,000 |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci | More than atoms in the universe |
| O(n!) | Factorial | Brute-force traveling salesperson | Even larger |
O(1): Constant Time
Whether your Python dict has ten keys or ten million, pulling one out by key costs about the same, and so does reading items[5] from a list. That flatness is the whole point of constant time.
O(log n): Logarithmic Time
I think of these as the "guess the number between 1 and 100" algorithms, where every guess rules out half of what's left. Binary search does exactly that on a sorted list:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
With a billion sorted items it needs about 30 comparisons, while plodding through them one by one could take the full billion, and I've never quite stopped finding that funny.
O(n) and O(n log n)
A linear algorithm visits each element a fixed number of times, the way you would if you were hunting for the biggest number in a spreadsheet column by eye. O(n log n) is the home of decent sorting. Merge sort splits the list down to single items (log n levels of splitting) and then does one linear pass per level while merging, so its running time stays put whether the data arrives sorted or scrambled.
O(n²) and Worse
Quadratic code nearly always has a loop tucked inside another loop, like this duplicate check that compares every pair:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
Exponential and factorial growth are worse by a mile. The textbook recursive Fibonacci keeps solving the same subproblems over and over, so every +1 on n roughly doubles the work. At n = 20 you won't notice; at n = 60 you can go cook dinner, eat it, wash up, and it still won't be done.
How to Calculate Time Complexity Step by Step
You almost never need a formal proof to calculate time complexity. I run through this list in my head and it covers most code I see:
- Define n. Decide what the input size is: the length of a list, the number of nodes in a graph, the number of digits in a number.
- Count the work in each line. Simple statements (assignments, comparisons, arithmetic) cost O(1).
- Add sequential blocks. Two loops one after another, each over n, give n + n = 2n.
- Multiply nested blocks. A loop over n inside another loop over n gives n × n = n².
- Drop constants. 2n becomes n, and 500 becomes 1.
- Keep only the dominant term. In n² + n, the n² part dwarfs the rest as n grows.
Quick worked one. Your count comes out to T(n) = 3n² + 5n + 2. Stick in a million: 3n² is three trillion, 5n is five million. Rounding error. Call it O(n²), done.
Loops that skip around instead of stepping by one are sneakier:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Every pass cuts n in half, so this while loop gives up after roughly log₂(n) rounds. Which is basically the whole answer to "when is time complexity O(log n)?" If what's left shrinks by a constant factor each step, you're there.
Recursion wants one more tool, a recurrence. Merge sort does two half-size jobs and then a merge, so T(n) = 2T(n/2) + n. The master theorem is a cheat sheet for recurrences of that shape, and for this one it spits out O(n log n).
And a rule of thumb from competitive programming I lean on a lot: a normal machine gets through something like 10⁸ simple operations a second. Very rough, but it's enough to sanity-check the time complexity of a solution before you hit submit. With n at 10⁵, O(n²) is about 10¹⁰ operations, so you time out. O(n log n) is under 2 million. Sails through.
Worst Case, Best Case and Average Case Analysis
Feed the same algorithm different input and the amount of work can swing wildly. Linear search shows it nicely:
- Best case: what you want is sitting right at the front. One comparison and you're out.
- Worst case: it's at the very end, or not there at all. That's n comparisons.
- Average case: if it could be anywhere with equal odds, you'll check around n/2 on average. Still O(n), mind you.
Ask a developer about "the complexity" of something and they'll nearly always give you worst-case time complexity, because that number is a promise you can plan around.
Say your API handles a request in O(n) at worst. Great, now you know how the slowest request behaves, and you're also covered when somebody sends you garbage on purpose. People absolutely do this: if an attacker works out which keys make your hash table collide, those are the only keys you'll be seeing for a while.
The average case is worth a look when the bad scenario hardly ever turns up. Quicksort is the poster child here, averaging O(n log n) but sliding to O(n²) if you pick pivots naively on data that's already sorted. Standard libraries work around that with random pivots, or by switching to a different sorting algorithm once the recursion goes suspiciously deep.
What Is Space Complexity and Auxiliary Space?
Memory is the other bill an algorithm runs up. Space complexity tracks how much of it you need as the input size grows, and you write it with the same Big O notation as time.
Part of that memory is the input itself, which you're paying for no matter what you do with it. The part you actually control is called auxiliary space, meaning the extra stuff your code allocates while it works, like temp variables and new arrays, plus the call stack that nobody remembers until it bites them.
Some quick cases:
- Swapping two variables needs a couple of slots regardless of anything else, so it's O(1) auxiliary space.
- Copying a list of n items into a fresh list costs you O(n) extra memory.
- Recursing n levels deep leaves n frames sitting on the stack, which is O(n) space even though you never built an array.
I watched a junior dev lose an afternoon to that last one. Their recursive function looked like it used no memory at all, but every unfinished call was parked on the stack waiting for the deeper ones to return, and on a big input the whole thing died with a stack overflow.
A lot of optimization is just trading memory for time or the other way round. Memoization caches results you've already computed, which takes naive Fibonacci from O(2ⁿ) down to O(n) time in exchange for O(n) memory. Hash tables buy you O(1) average lookups by spending space on buckets. On a server with 64 GB of RAM that trade is usually a no-brainer, but on a microcontroller or inside a smart contract you'd think twice.
Time and Space Complexity of Common Data Structures
Picking the right data structure usually beats micro-tuning whatever's inside your loop. Average-case costs for the ones you'll reach for most:
| Data structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked list | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash table | n/a | O(1) | O(1) | O(1) | O(n) |
| Balanced binary search tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Binary heap | O(1) for min/max | O(n) | O(log n) | O(log n) | O(n) |
Two footnotes. Linked list inserts and deletes are only O(1) if you're already holding the node. And a hash table can sink to O(n) when lots of keys collide.
Sorting algorithms vary just as much:
| Sorting algorithm | Best | Average | Worst | Auxiliary space |
|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
Merge sort is predictable but wants extra memory. Heap sort sorts in place and keeps the same worst case. Quicksort, despite the uglier ceiling, tends to win in practice.
Time Complexity in Blockchain and Smart Contracts
Here's where it gets fun. On your own server, a sloppy algorithm wastes CPU and maybe annoys a user. On Ethereum or any EVM chain, it wastes money. Every opcode a smart contract executes costs gas, paid in the chain's native coin, so your operation count shows up as a line on somebody's bill. Bad time complexity, in other words, comes with a price tag.
Say you've got a contract that loops over every token holder to pay out rewards. O(n), and gas creeps up with each new holder. On launch day nobody notices.
Then the holder list keeps growing. One day the payout needs more gas than the block gas limit, which is the cap on how much gas a single block can fit. After that the transaction can't go through. Not "it's slow." It just never succeeds, and whatever funds were waiting behind that function are basically stuck. Auditors file unbounded loops like this under denial-of-service, and fair enough.
The fixes are complexity thinking, pure and simple:
- Split the work into fixed-size batches over several transactions.
- Flip it around so each user claims their own reward. Every call is O(1).
- Swap the loop for a Merkle proof.
I love Merkle proofs as an example of why log n matters so much on-chain. A Merkle tree hashes a big pile of data up into one root hash.
To prove one entry belongs to a set of n, you need about log₂(n) hashes. For a million entries that's roughly 20. Not a million. Airdrops lean on this, and light Bitcoin wallets use the same trick to confirm a transaction without downloading the entire block.
Off-chain, same deal. Picture a payment backend that matches each incoming blockchain transaction to an invoice by scanning every open one. O(n) per payment, and it gets slower as the shop grows. Put the invoices in a hash map keyed by address or ID and each match is O(1). And if you'd rather not build and babysit that plumbing yourself, a crypto payment gateway such as Plisio does it for you.
