What time complexity measures
Time complexity describes how the work a program does grows as its input grows. It doesn't measure seconds. The same code runs faster on a fast machine and slower on a slow one, but the way its work scales with the input stays the same. Big O notation is the shorthand for that scaling: O(n) says the work grows in step with n, the size of the input.
The reason to care is in the chapters ahead. Many problems have a simple solution that is too slow for large inputs and a smarter one that is fast. Big O lets you tell them apart before you run anything.
Counting operations
To find the complexity of a piece of code, count how many basic steps it takes for an input of size n. Here is a method that adds up the elements of an array:
def sum(nums: Array[Int]): Int = {
var total = 0
for (n <- nums) {
total += n
}
return total
}
The assignment var total = 0 and the return each happen once. The line total += n runs once for every element. For an array of n elements the total is about n + 2 steps. Calling sum(Array(5, 3, 8)) returns 16 after three passes through the loop.
Linear time: O(n)
A method whose work grows in direct proportion to the input is linear, written O(n). Doubling the array doubles the number of loop passes. The method sum is linear. So is any method with a single loop over the input that does a constant amount of work per element: finding the largest element, counting the elements that match a condition, or searching for a value from left to right.
Why constants and small terms are dropped
The count for sum was n + 2. Big O keeps only the part that dominates for large n. For an array of a million elements, the extra 2 steps are noise. So n + 2 is O(n).
The same rule drops constant factors. A loop that does five operations per element takes 5n steps. That is still O(n), because doubling the input still doubles the work. Big O does not say that two linear methods take equally long, only that they scale the same way.
Nested loops: O(n squared)
When a loop sits inside another loop over the same input, the counts multiply:
def countPairs(nums: Array[Int]): Int = {
var count = 0
for (i <- nums.indices) {
for (j <- nums.indices) {
count += 1
}
}
return count
}
For an array of 3 elements, the inner line runs 3 times for each of the 3 passes of the outer loop, so countPairs returns 9. In general it runs n * n times. This is quadratic time, written O(n²). Doubling the input quadruples the work, which is why nested loops over large inputs get slow quickly.
A loop that halves: O(log n)
If each pass cuts the remaining work in half, the number of passes is only about the number of times you can halve n before reaching 1:
def halvings(n: Int): Int = {
var x = n
var steps = 0
while (x > 1) {
x /= 2
steps += 1
}
return steps
}
With n = 1024 the method returns 10, and with n = 1000000 it returns 19. A million times more input costs only nine more steps. This is logarithmic time, O(log n), the growth of a binary search.
Comparing growth
From slowest growing to fastest, the common classes are:
O(1): constant, independent of the input size;O(log n): logarithmic, as when halving;O(n): linear, one pass over the input;O(n log n): what good sorting algorithms take;O(n²): quadratic, nested loops over the input.
Big O describes the worst case unless you say otherwise. A search that may stop at the first element is still O(n), because the value could be last or missing.
Using it in this chapter
Each problem in this chapter states the complexity your solution should meet, for example O(n) time and O(1) extra space. Time is about the number of steps. Space is about the extra memory your solution allocates beyond its input, such as a new list that grows with n. A single pass that keeps a few variables meets O(n) time and O(1) space. A loop that builds a result list of n items uses O(n) space.
Key takeaways
- Big O describes how the work grows with the input size, not how many seconds it takes.
- Count the steps, then keep only the fastest-growing term and drop constant factors.
- One loop over the input is
O(n); a loop nested in another isO(n²); a loop that halves isO(log n).
