Time and Space Complexity Explained with C# Examples

1. What is Time Complexity?

Time complexity measures how the number of steps your algorithm takes grows as the input size grows.

• Fast algorithms grow slowly in steps as input increases.
• Slow algorithms grow quickly in steps.

Example:

• If doubling the number of items doubles the time → O(n).
• If doubling the number of items quadruples the time → O(n²).

---

2. What is Space Complexity?

Space complexity measures how much extra memory your algorithm needs relative to input size.

• Includes:

  • Variables
  • Data structures
  • Function call stack
  • Recursion overhead

Example:

• If your algorithm just counts numbers and stores a single integer → O(1) space.
• If it stores all numbers in a list → O(n) space.

---

3. Big-O Notation & Common Complexities

We’ll go through O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).

---

O(1) — Constant Time

Meaning: Execution time does not depend on input size.

Example in C#:

1public int GetFirstElement(int[] arr)
2{
3    return arr[0]; // Always one step
4}

Time Complexity: O(1) Space Complexity: O(1) (only one variable)

Diagram:

Steps
│     █████
│     █████
│     █████
└────────────── Input Size

---

O(log n) — Logarithmic Time

Meaning: Each step cuts the problem size by a fraction (usually half).

Example in C#: Binary Search

1public int BinarySearch(int[] arr, int target)
2{
3    int left = 0, right = arr.Length - 1;
4
5    while (left <= right)
6    {
7        int mid = (left + right) / 2;
8
9        if (arr[mid] == target) return mid;
10        if (arr[mid] < target) left = mid + 1;
11        else right = mid - 1;
12    }
13
14    return -1;
15}

Time Complexity: O(log n) Space Complexity: O(1)

Diagram:

Steps
│ ████
│  ███
│   ██
│    █
└────────────── Input Size

---

O(n) — Linear Time

Meaning: Steps increase in direct proportion to input size.

Example in C#:

1public int SumArray(int[] arr)
2{
3    int sum = 0;
4    foreach (int num in arr)
5    {
6        sum += num; // Runs once per element
7    }
8    return sum;
9}

Time Complexity: O(n) Space Complexity: O(1) (just sum variable)

Diagram:

Steps
│     █
│    ██
│   ███
│  ████
└────────────── Input Size

---

O(n log n) — Linearithmic Time

Meaning: Common in efficient sorting algorithms.

Example in C#: Merge Sort

1public void MergeSort(int[] arr)
2{
3    if (arr.Length <= 1) return;
4
5    int mid = arr.Length / 2;
6    int[] left = arr[..mid];
7    int[] right = arr[mid..];
8
9    MergeSort(left);
10    MergeSort(right);
11    Merge(arr, left, right);
12}
13
14private void Merge(int[] arr, int[] left, int[] right)
15{
16    int i = 0, j = 0, k = 0;
17    while (i < left.Length && j < right.Length)
18    {
19        if (left[i] < right[j]) arr[k++] = left[i++];
20        else arr[k++] = right[j++];
21    }
22    while (i < left.Length) arr[k++] = left[i++];
23    while (j < right.Length) arr[k++] = right[j++];
24}

Time Complexity: O(n log n) Space Complexity: O(n) (temporary arrays)

Diagram:

Steps
│     █
│    ███
│   █████
│  ███████
└────────────── Input Size

---

O(n²) — Quadratic Time

Meaning: Steps grow with the square of input size (nested loops).

Example in C#:

1public void PrintAllPairs(int[] arr)
2{
3    for (int i = 0; i < arr.Length; i++)
4    {
5        for (int j = 0; j < arr.Length; j++)
6        {
7            Console.WriteLine($"{arr[i]}, {arr[j]}");
8        }
9    }
10}

Time Complexity: O(n²) Space Complexity: O(1)

Diagram:

Steps
│     █
│    ███
│   █████
│  ████████
└────────────── Input Size

---

O(2ⁿ) — Exponential Time

Meaning: Doubles with every extra input (very slow).

Example in C#: Fibonacci (recursive)

1public int Fibonacci(int n)
2{
3    if (n <= 1) return n;
4    return Fibonacci(n - 1) + Fibonacci(n - 2);
5}

Time Complexity: O(2ⁿ) Space Complexity: O(n) (recursion call stack)

Diagram:

Steps
│     █
│      ██
│        ████
│            ████████
└────────────── Input Size

---

4. Summary Table

Complexity	Name	Example	Time Growth	Space Growth
O(1)	Constant	Access first element	Fixed	Fixed
O(log n)	Logarithmic	Binary Search	Grows slowly	Fixed
O(n)	Linear	Loop through array	Direct proportion	Fixed
O(n log n)	Linearithmic	Merge Sort	Slightly more than linear	Grows with n
O(n²)	Quadratic	Nested loops	Square of input	Fixed
O(2ⁿ)	Exponential	Recursive Fibonacci	Explodes with small n	Grows with n