Big O Cheat Sheet — Time Complexity Chart

An algorithm is a set of well-defined instructions for solving a specific problem. You can solve these problems in various ways.

This means that the method you use to arrive at the same solution may differ from mine, but we should both get the same result.

Because there are various ways to solve a problem, there must be a way to evaluate these solutions or algorithms in terms of performance and efficiency (the time it will take for your algorithm to run/execute and the total amount of memory it will consume).

What is Big O?

Big O, also known as Big O notation, represents an algorithm’s worst-case complexity. It uses algebraic terms to describe the complexity of an algorithm.

Big O defines the runtime required to execute an algorithm by identifying how the performance of your algorithm will change as the input size grows. But it does not tell you how fast your algorithm’s runtime is.

Big O notation measures the efficiency and performance of your algorithm using time and space complexity.

What is Time Complexity?

n algorithm’s time complexity specifies how long it will take to execute an algorithm as a function of its input size.

Why is time complexity a function of its input size?

To perfectly grasp the concept of “as a function of input size,” imagine you have an algorithm that computes the sum of numbers based on your input. If your input is 4, it will add 1+2+3+4 to output 10; if your input is 5, it will output 15 (meaning 1+2+3+4+5).

In the code above, we have three statements:

In Big O, there are six major types of complexities (time and space):

• Constant: O(1)
• Linear time: O(n)
• Logarithmic time: O(n log n)
• Quadratic time: O(n²)
• Exponential time: O(2^n)
• Factorial time: O(n!)

The Big O chart above shows that O(1), which stands for constant time complexity, is the best. This implies that your algorithm processes only one statement without any iteration. Then there’s O(log n), which is good, and others like it, as shown below:

• O(1) — Excellent/Best
• O(log n) — Good
• O(n) — Fair
• O(n log n) — Bad
• O(n²), O(2^n) and O(n!) — Horrible/Worst

This is enough for today. I will tell you more about that in the future.