# 📘 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)

```csharp
int x = arr[0]; // Accessing by index
```

### 🟦 Linear Time – O(n)

```csharp
for (int i = 0; i < arr.Length; i++)
    Console.WriteLine(arr[i]);
```

### 🟥 Quadratic Time – O(n²)

```csharp
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        sum += i * j;
```

### 🟨 Logarithmic Time – O(log n)

```csharp
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)

```text
Runtime growth vs Input size n

│
│                                O(n²)
│                      O(n log n)
│             O(n)
│        O(log n)
│ O(1)
└────────────────────────────────────────── n
```

**Interpretation:**  
- **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)*

---