Big O Notation explained

Introduction

Big O notation measures how fast your code runs as the number of inputs grows.
It’s really important to understand the following algorithms and try to apply the most performatic ones in your solutions. I will order them from fastest to slowest:

O(1) — Constant Time

When using O(1), it doesn’t matter the size of your input, the code will always take the same time to run.

var users = new Dictionary<int, string> {
    { 1, "Caique" },
    { 2, "Maria" },
    { 3, "Fernanda" },
};
var user = users[1];

In this example, it doesn’t matter the size of the collection, accessing a dictionary by key is constant.

O(log n) — Logarithmic Time

Always divides the problem in half at each step. The most common example is a binary search.

int BinarySearch(int[] array, int target) {
    int left = 0;
    int right = array.Length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (array[mid] == target)
            return mid;

        if (array[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

This one is very efficient when your data is ordered.

O(n) — Linear Time

In linear time, the execution time grows in the exact same proportion as the input length.

var users = new List<string> { "Caique", "Maria", "Fernanda" };

foreach (var user in users) {
    Console.WriteLine(user); 
}

In the example above, if the input length grows by 10%, the execution time grows the same.

O(n log n) — Linearithmic Time

Used in most common sorting algorithms.

var numbers = new List<int> { 5, 2, 8, 1, 3 };

numbers.Sort(); 

In the example above, the code is performing a merge sort. This complexity is also seen in algorithms like quicksort.

O(n²) — Quadratic Time

This is the main villain in many codebases. The execution time grows very fast as the input length increases.

var users = new List<string> { "Caique", "Maria", "Fernanda" };

foreach (var user1 in users) {
    foreach (var user2 in users) {
        Console.WriteLine($"{user1} - {user2}"); 
    }
}

It’s usually caused by a loop inside another loop. Always try to avoid doing something like that.

Conclusion

If you code, it doesn’t matter if it’s frontend or backend, it’s great to know these algorithms to prevent or diagnose performance issues in your program.