Understanding Big O Complexity in C#

Posted by Rodrigo Castro on August 4, 2025

Introduction

Big O Notation is a fundamental concept in computer science and a common topic in coding interviews. It describes how an algorithm performs as the input size grows, focusing on time complexity and space complexity. In this post, we’ll break down the most common Big O notations with real C# examples, so you can not only understand the theory but also apply it in your everyday .NET development.

Time vs Space Complexity

  • Time Complexity measures how execution time grows with input size.
  • Space Complexity measures how memory consumption grows with input size.

We represent the input size with n, and we focus on how the algorithm behaves as n → ∞. We’re interested in the worst-case performance, because that’s what impacts scalability.

Common Big O Notations in C#

O(1) – Constant Time

An operation that does not scale with input size.

1
2
3
4
int GetFirstElement(int[] array)
{
    return array[0]; // always takes the same time
}

Looking up by index in an array or List<T> is usually O(1).

O(log n) – Logarithmic Time

This typically occurs in divide-and-conquer algorithms, like binary search.

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

Each step cuts the data set in half, making it very efficient even for large n.

O(n) – Linear Time

The time grows proportionally to the input size.

1
2
3
4
5
6
7
8
bool Contains(int[] array, int value)
{
    foreach (var item in array)
    {
        if (item == value) return true;
    }
    return false;
}

Used frequently in iteration and traversal scenarios.

O(n²) – Quadratic Time

Often the result of nested loops over the same input set.

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

Be cautious with algorithms that scale this way, especially with large datasets.

O(2ⁿ) – Exponential Time

Occurs in algorithms that generate all possible combinations or subsets.

1
2
3
4
5
6
7
8
9
10
void GenerateSubsets(string prefix, string remaining)
{
    if (string.IsNullOrEmpty(remaining))
    {
        Console.WriteLine(prefix);
        return;
    }
    GenerateSubsets(prefix + remaining[0], remaining.Substring(1));
    GenerateSubsets(prefix, remaining.Substring(1));
}

This quickly becomes infeasible as n increases.

Simplifying Big O Expressions

When analyzing an algorithm, focus on the dominant term:

1
// O(n² + n) => O(n²)

You always drop lower-order terms and constants because they have less impact on scaling behavior.

Interview Tips

  • When asked to analyze complexity, identify loops and recursion.
  • Prefer using efficient collections like Dictionary<TKey, TValue> which offer O(1) access in average case.
  • Practice identifying complexity in your own code and rewriting inefficient portions.
  • Some interviewers may ask about space complexity, so always consider allocations (new arrays, recursive calls, etc.).

Conclusion

Understanding Big O helps you write faster, more scalable .NET applications and makes you a stronger problem solver in interviews. Next time you write a loop or recursion in C#, ask yourself: how does this scale?