Why this lesson matters
Some lines of C# look like one cheap step but do work proportional to the data they touch. Taking part of a string, copying part of an array and gluing two strings together all hide a loop. Big O notation should count that loop, so you need to know which operations copy and which don't.
This lesson goes through slicing and concatenation and shows how a harmless-looking line can turn a linear algorithm into a quadratic one.
Slicing a string: Substring
A string in C# is immutable, so a piece of a string can't share the original's memory. Substring allocates a new string and copies the characters into it:
string s = "algocademy";
string a = s.Substring(2, 4); // "goca"
string b = s[2..6]; // "goca", the range form calls Substring for you
Copying k characters costs O(k) time and O(k) extra space. When you slice off almost the whole string, k is about n, so the slice is O(n). Only the empty slice is free.
Slicing an array: ranges, Array.Copy and GetRange
Arrays behave the same way. A range expression on an array creates a new array and copies the elements, so the two arrays are independent:
int[] arr = { 10, 20, 30, 40, 50 };
int[] part = arr[1..4]; // new array { 20, 30, 40 }
part[0] = 99;
Console.WriteLine(string.Join(",", part)); // 99,30,40
Console.WriteLine(string.Join(",", arr)); // 10,20,30,40,50
Changing part left arr alone, which proves the elements were copied. The same O(k) cost applies to Array.Copy and to list.GetRange(start, count) on a List<T>.
Slices that don't copy: Span
If you only need to read or change a part of an array or string, a Span<T> (or ReadOnlySpan<char> for text) is a view over the existing memory. Creating one is O(1), because nothing is copied:
int[] arr = { 10, 20, 30, 40, 50 };
Span<int> view = arr.AsSpan(1, 3);
view[0] = 99;
Console.WriteLine(string.Join(",", arr)); // 10,99,30,40,50
Writing through the view changed arr, because both refer to the same memory. That is the trade-off: no copy, but no independence either.
Concatenation
Joining two strings with + builds a third string that holds both. If the operands have lengths n and m, the work is O(n + m). Neither operand is changed, because strings are immutable. Adding one character to a string of length n therefore costs O(n), not O(1).
Several operands in one expression, such as "ab" + "cd" + 1 + 'x', are compiled into a single concatenation call, which allocates one result. The cost is still proportional to the total length.
The trap: concatenation in a loop
Now put += in a loop:
static string BuildSlow(int n) {
string s = "";
for (int i = 0; i < n; i++) {
s += "x";
}
return s;
}
On iteration i the string has i characters, and += copies all of them into a new string of i + 1 characters. The total number of characters copied is:
0 + 1 + 2 + ... + (n - 1) = n * (n - 1) / 2
That is O(n²) for a loop that looks like it does n simple steps. The fix is StringBuilder, which keeps a growable buffer and appends in amortized O(1) per character:
static string BuildFast(int n) {
var sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.Append('x');
}
return sb.ToString();
}
Both methods return the same string. BuildFast runs in O(n) time, because the final ToString() copies the characters once. StringBuilder lives in System.Text. When you already have all the pieces in a collection, string.Join(", ", pieces) does the whole job in one pass as well.
Quick reference
| Operation | Time |
|---|---|
s.Substring(start, k) or s[a..b] | O(k) |
arr[a..b], Array.Copy, list.GetRange | O(k) |
arr.AsSpan(start, k) | O(1) |
s1 + s2 | O(n + m) |
s += "x" inside a loop of n steps | O(n²) in total |
sb.Append(...) inside a loop of n steps | O(n) in total |
Slices inside loops
The same reasoning applies when a slice appears inside a loop. Taking s.Substring(i) on every iteration of a loop over n characters copies n - i characters each time, which adds up to O(n²). If a loop only needs to compare characters, index the string with s[i], which is O(1) and copies nothing.
Key takeaways
- A slice that copies costs time and space proportional to its length.
- A
Spanis a view, so creating one isO(1), but it shares memory with the original. - Strings are immutable, so every concatenation builds a new string of the combined length.
- Repeated
+=on a string inside a loop is quadratic; useStringBuilderorstring.Joininstead. - When you analyze a loop, count what each line costs, not just how many lines there are.