📘 Algorithm Complexity Cheat Sheet
A visual and practical overview for understanding algorithmic complexity (Big O notation).
Prepared for the course "Algorithms and Data Structures in C# (.NET)"
👨🏫 Dr. Stoyan Cheresharov, Plovdiv University “Paisii Hilendarski”
🧠 What Is Big O Notation?
Big O notation describes how the runtime or memory usage of an algorithm grows as the input size (n) increases.
The O stands for Order — it represents the upper bound (worst-case growth rate).
🔢 Why Do We Use It?
Big O lets us compare algorithms independently of hardware or language.
It shows how fast an algorithm’s runtime grows when the problem size increases.
⚙️ Common Complexities
| Big-O | Name | Example | Meaning |
|---|---|---|---|
| O(1) | Constant | Access array element | Same time regardless of input size |
| O(log n) | Logarithmic | Binary Search | Work halves each step |
| O(n) | Linear | Simple loop | Work grows directly with input size |
| O(n log n) | Quasi-linear | Merge Sort | Typical for efficient sorting |
| O(n²) | Quadratic | Nested loops | Slower as size doubles |
| O(2ⁿ) | Exponential | Recursive Fibonacci | Work doubles each time n increases |
| O(n!) | Factorial | Permutations | Tests all possible orderings |
💻 C# Examples
🟩 Constant Time – O(1)
int x = arr[0]; // Accessing by index🟦 Linear Time – O(n)
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);🟥 Quadratic Time – O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum += i * j;🟨 Logarithmic Time – O(log n)
int BinarySearch(int[] arr, int x)
{
int low = 0, high = arr.Length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}📈 Growth Visualization (Conceptual)
Runtime growth vs Input size n
│
│ O(n²)
│ O(n log n)
│ O(n)
│ O(log n)
│ O(1)
└────────────────────────────────────────── nInterpretation:
- O(1) → Instant (constant work)
- O(log n) → Slower growth (binary search)
- O(n) → Linear growth (single loop)
- O(n²) → Rapid growth (nested loops)
🧮 How Complexities Are Calculated
| Type | Example | Step Count | Result |
|---|---|---|---|
| Constant | arr[0] |
1 | O(1) |
| Linear | for (i < n) |
n | O(n) |
| Quadratic | for(i<n) for(j<n) |
n × n | O(n²) |
| Logarithmic | Binary search | log₂(n) | O(log n) |
| Quasi-linear | Merge sort | n × log₂(n) | O(n log n) |
🧠 Key Insights
✅ We ignore constants: O(3n + 10) → O(n)
✅ We keep only the dominant term: O(n² + n) → O(n²)
✅ Big O describes growth trend, not actual seconds.
✅ Focus on asymptotic behavior — as n → ∞.
🧩 Memory (Space) Complexity Examples
| Operation | Space Complexity |
|---|---|
| Simple variable | O(1) |
| Array of size n | O(n) |
| 2D matrix n×n | O(n²) |
⚖️ Real-world Analogy
| Complexity | Analogy |
|---|---|
| O(1) | Teleport — instant |
| O(log n) | Elevator — halves distance each step |
| O(n) | Walking — proportional to distance |
| O(n log n) | Walking uphill |
| O(n²) | Searching every corner of every room |
| O(2ⁿ) | Checking every possible combination |
| O(n!) | Reordering everything in every possible way |
📊 Quick Comparison
| Complexity | 10 items | 100 items | 1000 items |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 |
| O(n) | 10 | 100 | 1000 |
| O(n log n) | 30 | 700 | 10,000 |
| O(n²) | 100 | 10,000 | 1,000,000 |
| O(2ⁿ) | 1024 | huge | impossible |
| O(n!) | 3,628,800 | impossible | impossible |
🧭 Summary
Big O is not about exact speed, it’s about how performance scales.
In short:
- Use O(1) when possible.
- Aim for O(n) or O(n log n) in practical algorithms.
- Avoid O(n²) and worse in large data sets.
📗 Prepared by: Dr. Stoyan Cheresharov
📍 Plovdiv University “Paisii Hilendarski”
🖥️ Course: Algorithms and Data Structures in C# (.NET)
