What time complexity measures
Time complexity describes how the amount of work a piece of code does grows as its input grows. It is not a stopwatch reading. A stopwatch depends on the computer, the JVM warm-up and whatever else is running. Complexity counts how many basic steps the code takes, as a function of the input size, usually called n.
Big O notation is the shorthand for that growth. O(n) reads "order of n": the work grows in proportion to n. Double the input and the work roughly doubles.
Linear time: O(n)
This function adds up the numbers in an array:
fun sum(nums: IntArray): Int {
var total = 0
for (n in nums) {
total += n
}
return total
}
The loop body runs once per element. For 10 elements it does about 10 additions, for 1,000 elements about 1,000. The work is proportional to nums.size, so sum is O(n), called linear time. Any function that must look at every element once, for example to find the largest, to count matches or to print everything, is linear.
Counting steps
You can make the growth visible by counting loop iterations:
fun countSteps(n: Int): Int {
var steps = 0
for (i in 0 until n) steps++
return steps
}
fun twoLoops(n: Int): Int {
var steps = 0
for (i in 0 until n) steps++
for (i in 0 until n) steps++
return steps
}
fun countPairs(n: Int): Int {
var steps = 0
for (i in 0 until n) for (j in 0 until n) steps++
return steps
}
Calling them with growing values of n gives:
| n | countSteps | twoLoops | countPairs |
|---|---|---|---|
| 10 | 10 | 20 | 100 |
| 100 | 100 | 200 | 10,000 |
| 1,000 | 1,000 | 2,000 | 1,000,000 |
countSteps grows in step with n: linear. twoLoops does twice as much work, but it still grows in a straight line, so it is also O(n). countPairs has a loop inside a loop, and ten times more input means a hundred times more work: that is O(n²), quadratic time.
The rules for reading Big O
- Drop constants.
2nandn + 5are bothO(n). Big O is about the shape of the growth. A function that loops twice is not a different kind of function from one that loops once. - Keep the dominant term. A function that does
n²steps and thennmore steps isO(n²), because for largenthe square outweighs the rest. - Loops one after another add; nested loops multiply. Two separate loops over
ngiven + n, which isO(n). A loop inside a loop givesn × n. - It describes the worst case by default. A search that stops as soon as it finds its target may finish early, but when the target is missing or last it examines all
nelements, so it isO(n).
Here is an example with an early exit:
fun containsDuplicate(nums: IntArray): Boolean {
for (i in nums.indices) {
for (j in i + 1 until nums.size) {
if (nums[i] == nums[j]) return true
}
}
return false
}
If the first two numbers are equal, it returns after one comparison. With no duplicates, every pair is compared, which is about n²/2 comparisons. Dropping the constant factor, the worst case is O(n²).
Space complexity
The same notation describes memory. sum uses one extra variable, total, no matter how large nums is, so its extra space is O(1). A function that builds a new list holding one entry per input element, such as one returning the reversed array, uses O(n) extra space.
Why this matters in the chapter
The problems ahead set limits on running time. For small inputs an O(n²) solution is fine. When n reaches the hundreds of thousands, quadratic code does billions of steps, while a linear one does hundreds of thousands. Learning to read complexity from the loops lets you see this before you run the code.
Key takeaways
- Big O describes how the number of steps grows with the input size
n. - One pass over the data is
O(n); a loop inside a loop over the same data is usuallyO(n²). - Ignore constant factors and smaller terms; say what the worst case is.
- Count extra memory the same way to get space complexity.