What time complexity measures
Time complexity describes how the work a piece of code does grows as its input grows. It doesn't measure seconds. The same method takes different times on different machines, but the number of steps it needs for an input of a given size is a property of the algorithm itself.
We call the input size n. For an array, n is its Length. For a string, it is the number of characters. Big O notation writes the growth rate as O(...) around a function of n. It gives an upper bound on how fast the work grows, and it keeps only the part that matters when n is large.
Linear time: O(n)
An algorithm is linear when doubling the input roughly doubles the work. The usual case is one pass over the data:
static int Sum(int[] nums) {
int total = 0;
foreach (int n in nums) {
total += n;
}
return total;
}
For an array with 5 elements the loop body runs 5 times, and for 5,000 elements it runs 5,000 times. Everything else in the method, the declaration of total and the return, happens once. Sum(new[] {3, 1, 4, 1, 5}) returns 14.
Finding the largest value is also linear:
static int Max(int[] nums) {
int best = nums[0];
for (int i = 1; i < nums.Length; i++) {
if (nums[i] > best) {
best = nums[i];
}
}
return best;
}
The loop makes n - 1 comparisons. The method has to look at every element, because any one of them could be the largest.
Ignoring constants and small terms
Big O drops details that don't change the shape of the growth:
- Constant factors. A loop that does three operations per element does 3n operations, and a loop that does one does n. Both are
O(n). - Lower-order terms. A method that does
nsteps and then 10 more isn + 10steps, which isO(n). For largenthe 10 doesn't matter. - Two passes. One loop followed by another loop over the same array is
2n, so stillO(n).
Different inputs can also mean different amounts of work. Big O usually describes the worst case. A search for a value in an array can stop on the first element if it matches, but if the value is missing or is the last element, it looks at all n. That is why the search is O(n).
The common growth rates
| Notation | Name | Typical C# example |
|---|---|---|
O(1) | constant | reading nums[i] |
O(log n) | logarithmic | binary search in a sorted array |
O(n) | linear | one loop over the data |
O(n log n) | linearithmic | sorting with Array.Sort |
O(n²) | quadratic | a loop nested inside a loop |
Moving down the table, the work grows faster. For 1,000 elements, a linear algorithm does about 1,000 steps and a quadratic one about 1,000,000.
A quadratic example
Nested loops over the same data multiply the work:
static bool HasDuplicate(int[] nums) {
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
In the worst case, when there is no duplicate, the inner loop runs about n²/2 times in total. The constant 1/2 is dropped, so the method is O(n²). For {1, 2, 3} it returns false after 3 comparisons, and for 6 elements with no duplicates it makes 15.
Why it matters in practice
Small inputs hide the difference. An O(n²) method on 100 elements is instant. On a million elements it needs about a trillion steps, which is far too slow, while an O(n) method needs a million. When you write a solution in this course, ask how many times the loops run relative to n. That question is how you choose between a simple approach and a faster one.
To estimate the complexity of your own code, count how many times the innermost statement runs for the largest input, then keep only the fastest-growing term.
Key takeaways
- Time complexity counts how the number of steps grows with the input size
n, not seconds. - One loop over
nitems isO(n), and a loop inside a loop is usuallyO(n²). - Constant factors and small terms are ignored, and the worst case is the usual measure.
- An array's
Lengthis thento count against.