Arrays and strings: what is cheap
Arrays and strings are stored as a block of consecutive items, so reaching any position is a direct jump. These operations are O(1):
- reading or writing
nums[i]; - reading
nums.Lengthors.Length, because the size is stored; - reading a character with
s[i].
Anything that has to look at, copy or build several items grows with their number. In the next table, n is the length of the array or string, and k is the length of the piece being handled.
| Operation | Cost |
|---|---|
Array.IndexOf(nums, x) | O(n) |
Array.Reverse(nums) | O(n) |
Array.Sort(nums) | O(n log n) |
Array.BinarySearch(nums, x) on a sorted array | O(log n) |
s.IndexOf(t), s.Contains(t) | O(n) for a short t (up to O(n·m) for a pattern of length m) |
s.Substring(start, k) | O(k), since it copies the piece |
s.Split(' '), s.Replace(a, b), s.ToCharArray() | O(n) |
string.Join(", ", items) | O(total length) |
s1 + s2 | O(length of both), because a new string is created |
Strings are immutable. No method changes s: Replace, Substring and + all return a new string. That is why they cost time proportional to the text they produce, and why concatenating in a loop gets expensive.
string s = "hello world";
Console.WriteLine(s.Length); // 11
Console.WriteLine(s[4]); // o
Console.WriteLine(s.IndexOf("wor")); // 6
Console.WriteLine(s.Substring(6, 5)); // world
Console.WriteLine(s.Replace("l", "L")); // heLLo worLd
Arrays have a fixed length. Appending to an array isn't possible; you would create a bigger array and copy every item, which is O(n). A List<T> does that copying for you occasionally, which is why its Add is O(1) on average.
What a logarithm is
A logarithm answers the question: how many times can you halve n before you reach 1? In computer science the base is 2, written log n or log₂ n. For n = 8 the answer is 3, because 8 becomes 4, then 2, then 1. In general, log₂ n is the power that 2 must be raised to in order to get n: 2³ = 8, so log₂ 8 = 3.
Counting the halvings in code gives the same numbers:
static int Halvings(int n) {
int steps = 0;
while (n > 1) {
n /= 2;
steps++;
}
return steps;
}
Integer division discards the remainder, so the count is the rounded-down logarithm. The results:
Halvings(8) = 3
Halvings(1000) = 9
Halvings(1000000) = 19
A million items need fewer than twenty halvings. That makes O(log n) very close to constant in practice, and it is the reason logarithmic algorithms are so valuable.
Where the logarithm shows up
Binary search is the classic case. In a sorted array, you compare the target with the middle item and throw away the half that can't contain it, then repeat. Each step halves the remaining range, so the search takes O(log n) steps instead of the O(n) of checking each item.
int[] arr = {5, 2, 9, 1};
Array.Sort(arr); // 1, 2, 5, 9
Console.WriteLine(Array.BinarySearch(arr, 5)); // 2
The array must be sorted first, or the result is meaningless. Sorting costs O(n log n), so sorting just to search once isn't worth it, while sorting once and searching many times is. If the value isn't found, Array.BinarySearch returns a negative number.
A binary search by hand
Take the sorted array {1, 2, 5, 9, 12, 15, 20} and look for 15. There are 7 items, indexes 0 to 6.
- The middle is index 3, which holds 9. Since 15 is larger, the left half and index 3 can't contain it. The range is now indexes 4 to 6.
- The middle of that range is index 5, which holds 15. Found.
Two comparisons were enough, where a left-to-right scan would have needed six. Doubling the array to 14 items adds only one more comparison in the worst case, which is the signature of O(log n).
The log n in O(n log n) comes from the same halving: efficient sorts split the data in half again and again, and do linear work at each level.
Reading growth rates
Here is how many steps each growth rate needs as the input gets bigger, using whole numbers for the logarithm:
| n | log n | n | n log n | n² |
|---|---|---|---|---|
| 16 | 4 | 16 | 64 | 256 |
| 1,024 | 10 | 1,024 | 10,240 | 1,048,576 |
When you read a solution, a loop that halves a range, such as while (lo <= hi) with the midpoint discarding half each time, signals a logarithm. A loop over every item signals n, and a call to a sort signals n log n.
Key takeaways
- Indexing arrays and strings, and reading
Length, areO(1). - Searching, copying, splitting and replacing are
O(n), and sorting isO(n log n). - Strings are immutable, so every string method that "changes" text builds a new string.
log ncounts how many times you can halven. A million items need about twenty halvings.- Binary search on a sorted array is
O(log n).