What time complexity measures
Two correct functions can differ enormously in how long they take on large inputs. Time complexity describes how the work a function does grows as its input grows. It does not measure seconds, because seconds depend on the machine. It counts how many basic steps the code takes as a function of the input size, usually called n.
Big O notation writes that growth in a short form. O(n) means the number of steps grows in proportion to n, O(1) means it doesn't grow at all, and O(n²) means it grows with the square of n. Big O keeps only the dominant term and drops constant factors, so 3n + 10 steps and 100n steps are both O(n).
In Go, n is usually len(nums) for a slice, or the length of a string.
Linear time: O(n)
A function runs in linear time when it touches each element a fixed number of times. Summing a slice is the standard example:
func sum(nums []int) int {
total := 0
for _, n := range nums {
total += n
}
return total
}
The loop body runs once per element. Calling sum([]int{4, 8, 15}) returns 27 after three passes. With a million elements, there are a million passes. Doubling the input doubles the work.
These are all linear as well:
- two loops one after another, each over the same slice, because
n + nis still proportional ton; - a loop that does a fixed amount of work per element, such as five arithmetic operations;
- a loop that stops early with
breakin the best case but may need the whole slice in the worst case. Big O normally describes the worst case.
Comparing linear and quadratic growth
A loop inside a loop usually multiplies the work. This function counts the pairs (i, j) with i < j:
func countPairs(n int) int {
steps := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
steps++
}
}
return steps
}
Compared with a single loop that counts to n, the number of steps looks like this:
| n | Single loop | Pairs |
|---|---|---|
| 10 | 10 | 45 |
| 100 | 100 | 4,950 |
| 1,000 | 1,000 | 499,500 |
The pair count is n(n-1)/2, which is O(n²): when the input grows ten times, the work grows about a hundred times. That is the practical meaning of Big O. A slower growth rate wins for large inputs, even if its constant factor is worse.
Applying it to Two Sum
The starter code in this chapter is the Two Sum problem: given nums and a target, find two indices whose values add up to the target. The method has this shape:
type Solution struct {}
func (this Solution) twoSum(nums []int, target int) []int {
}
The obvious solution tries every pair with two nested loops. That is the quadratic pattern above, so it takes O(n²) time. A faster solution keeps a map from each value seen so far to its index. For each number, it looks up target - v in the map, which takes constant time on average, so a single pass is enough:
func (this Solution) twoSumMap(nums []int, target int) []int {
seen := map[int]int{}
for i, v := range nums {
if j, ok := seen[target-v]; ok {
return []int{j, i}
}
seen[v] = i
}
return []int{-1, -1}
}
For nums = [2, 7, 11, 15] and target = 9, both versions return [0 1]. The map version is O(n) time, but it uses O(n) extra space for the map. Trading memory for time is a common pattern.
Go details that affect the count
- Hidden loops. Some single lines of Go do work proportional to the data. Copying a slice with
copy, building a string by concatenation, or searching withslices.Containseach hide a loop, and inside another loop they make the code quadratic. lenis free. For slices, strings and maps,lenreads a stored number and takesO(1), so writingi < len(nums)in a loop condition adds nothing.- Space counts too. The same notation describes memory.
sumusesO(1)extra space, and the map version above usesO(n).
Key takeaways
- Time complexity describes how the number of steps grows with the input size, not how many seconds a run takes.
- A single loop over
nelements, doing a fixed amount of work per element, isO(n). - Nested loops over the same data usually give
O(n²). - Big O drops constants and smaller terms, and normally describes the worst case.