Big-O and basic data structures
What Big-O notation is
Big-O describes how an algorithm's running time (or memory use) grows relative to the size of the input (n), in the worst case, ignoring constant factors and less significant terms.
// O(1) - constant time, regardless of the collection's size
int first = list[0];
// O(n) - time grows LINEARLY with the size
foreach (var item in list) { Console.WriteLine(item); }
// O(n²) - time grows QUADRATICALLY (a loop within a loop)
foreach (var a in list)
foreach (var b in list)
Compare(a, b);
// O(log n) - time grows logarithmically (e.g. binary search)
int index = Array.BinarySearch(sortedArray, target);
Complexities of basic operations on .NET collections
| Operation | List<T> |
Dictionary<K,V> |
HashSet<T> |
LinkedList<T> |
|---|---|---|---|---|
| Access by index | O(1) | - | - | O(n) |
| Search by value | O(n) | O(1)* | O(1)* | O(n) |
| Add at the end | O(1)** | O(1)* | O(1)* | O(1) |
| Add at the start/in the middle | O(n) | - | - | O(1) |
| Removal | O(n) | O(1)* | O(1)* | O(1) |
Amortised O(1) for hashed structures - in practice almost always constant time, but in rare collision cases it can be worse.
*List<T>.Add() is amortised O(1) - sometimes the internal array has to be enlarged, which is O(n), but it happens rarely.
What the O(...) notation actually means
"O" comes from "Order of" (the order of magnitude) - a mathematical notation describing how fast an algorithm's running time (or memory) grows as the size of the input grows. It doesn't say how many milliseconds that is exactly - it speaks about the rate of growth relative to n.
n is always the size of the input - the number of elements in an array, the number of rows in a database, the length of a string - whatever "scales" in your problem.
The key intuition: Big-O answers the question "what happens if I double the input?" - not "how fast it runs for 10 elements", but "how the behaviour changes as n grows towards infinity".
O(1) - constant time
The running time doesn't depend on n - whether you have 10 elements or 10 million, the operation takes the same amount of time.
int[] numbers = new int[1_000_000];
int first = numbers[0]; // O(1) - access by index, ALWAYS one step
int last = numbers[^1]; // O(1) - the same, regardless of the array's size
bool isEmpty = numbers.Length == 0; // O(1) - Length is already stored, not recomputed
An important conceptual trap: O(1) doesn't mean "fast" in an absolute sense - it only means "a constant number of steps". Something that does 1000 operations, but always 1000, regardless of n, is still O(1):
// This IS O(1), even though it does 1000 iterations - the number of iterations is CONSTANT, it doesn't depend on n
int Sum1000FixedNumbers()
{
int sum = 0;
for (int i = 0; i < 1000; i++) sum += i; // ALWAYS 1000, whatever the input
return sum;
}
O(n) - linear time
The running time grows proportionally to n - if you double the input, the operation will take (roughly) twice as long.
int Sum(int[] array) // O(n)
{
int sum = 0;
foreach (var n in array) // MUST visit EVERY element - once
sum += n;
return sum;
}
For an array of 10 elements - 10 steps. For 1000 elements - 1000 steps. For a million - a million steps. The number of operations scales together with n, 1:1 (hence "linear" - like a line on a chart).
bool Contains(int[] array, int target) // O(n) - w NAJGORSZYM przypadku
{
foreach (var n in array)
if (n == target) return true; // may find it right away (best case), or only at the end (worst case)
return false;
}
Important: Big-O usually describes the worst case - Contains may theoretically find the element in the first position (1 step), but Big-O talks about the upper bound, i.e. the situation when you have to look through everything (the element is at the end or isn't there).
A visual comparison - how they grow with n
n (the data size) |
O(1) - number of steps | O(n) - number of steps |
|---|---|---|
| 10 | 1 | 10 |
| 100 | 1 | 100 |
| 10 000 | 1 | 10 000 |
| 1 000 000 | 1 | 1 000 000 |
O(1) is a flat line on a chart - always the same height. O(n) is a diagonal line - it grows evenly with n.
A common mistake - "one loop = automatically O(n)"
This is a simplification that is sometimes true, but not always - what matters is how many times you visit n elements, not the number of loops in the code:
// ONE loop, and O(n) - visits every element ONCE
foreach (var x in array) { Console.WriteLine(x); }
// TWO loops, but STILL O(n) - each loop separately goes through n, so n + n = 2n,
// and constant factors (2) are IGNORED in Big-O
foreach (var x in array) { /* ... */ }
foreach (var x in array) { /* ... */ }
// ONE loop, but O(1) - the number of iterations has a CONSTANT UPPER LIMIT, independent of "n"
int[] fixedFive = { 1, 2, 3, 4, 5 };
for (int i = 0; i < fixedFive.Length; i++)
{
Console.WriteLine(fixedFive[i]); // fixedFive.Length jest ZAWSZE 5, nie zmienna "n"
}
The last example is, incidentally, a common trick question: "Is a for loop always O(n)?" - the answer: no, what matters is whether the loop's upper bound depends on the input size or is a constant. A loop over an array of an always-known, fixed size (here: 5) is O(1), even though technically it is a "loop over an array".
A subtler case - a loop bounded by Math.Min():
// Still O(1) - the number of iterations is BOUNDED FROM ABOVE by a constant (5),
// even though the expression refers to array.Length
int limit = Math.Min(5, array.Length);
for (int i = 0; i < limit; i++)
{
Console.WriteLine(array[i]);
}
If array.Length = 3 → limit = 3 → 3 steps
If array.Length = 1000 → limit = 5 → 5 steps (bounded by the constant!)
If array.Length = 10 000 → limit = 5 → 5 steps (bounded by the constant!)
This is exactly the same mechanism that e.g. Take(5) in LINQ is based on - it takes at most 5 elements, regardless of whether the collection has 5 or 5 million.
Why we ignore constant factors
2n and n are still the same O(n) - Big-O is interested in the rate of growth, not the precise number of operations. For large n, the difference between n and 2n (double) is insignificant compared to the difference between n and n² (the square) - the latter grows far faster, and that is the heart of what Big-O tells you.
n = 1000:
2n = 2 000
n = 1 000
n² = 1 000 000 ← O(n²) is dramatically worse, regardless of constant factors
A practical example - why this matters
// ❌ O(n²) - for each order, it SEARCHES the whole list of customers
public List<OrderWithCustomer> Combine(List<Order> orders, List<Customer> customers)
{
var result = new List<OrderWithCustomer>();
foreach (var order in orders) // n razy
{
var customer = customers.FirstOrDefault(c => c.Id == order.CustomerId); // m operacji - LINIOWE przeszukanie!
result.Add(new OrderWithCustomer(order, customer));
}
return result;
} // Overall: O(n * m)
// ✅ O(n) - building the dictionary once, then O(1) access
public List<OrderWithCustomer> Combine(List<Order> orders, List<Customer> customers)
{
var customerById = customers.ToDictionary(c => c.Id); // O(m) - JEDEN raz
var result = new List<OrderWithCustomer>();
foreach (var order in orders) // n razy
{
customerById.TryGetValue(order.CustomerId, out var customer); // O(1) for each lookup!
result.Add(new OrderWithCustomer(order, customer));
}
return result;
} // Overall: O(n + m)
For 10 000 orders and 1000 customers: the first version is 10 million comparison operations, the second is 11 000. That is a difference which in production goes from "runs instantly" to "a timeout after 30 seconds".
Space complexity
Big-O also describes memory use, not just time:
// O(1) of additional memory - modifies in place
void ReverseInPlace(int[] array)
{
Array.Reverse(array);
}
// O(n) of additional memory - creates a NEW array
int[] ReverseCopy(int[] array)
{
return array.Reverse().ToArray();
}
Typical complexity classes - from best to worst
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
constant logarithm. linear linear-log. quadr. expon. factorial
Practical examples of algorithms:
- O(log n) - binary search in a sorted array
- O(n log n) - efficient sorting algorithms (Array.Sort, quicksort, mergesort)
- O(n²) - naive bubble sort, nested loops over the same collection
Why this matters in SE III interviews
This is not a question about "knowing theory for theory's sake" - in practice it is about recognising specific anti-patterns in code, like the FirstOrDefault in a loop example above. The most common trick question: "What is wrong with this code?" with a snippet containing a nested Where/FirstOrDefault over an unindexed collection - a good answer recognises the quadratic complexity and proposes a Dictionary/HashSet as the solution.