Big-O Notation Cheat Sheet: quick answers to Big-O questions

What is Big O Notation?

Big O Notation is a mathematical function used in computer science to describe an algorithm’s complexity. It is usually a measure of the runtime required for an algorithm’s execution.

But, instead of telling you how fast or slow an algorithm’s runtime is, it tells you how an algorithm’s performance changes with the size of the input (size n).

The biggest factors that affect Big O are the number of steps and the number of iterations the program takes in repeating structures like the for loop.

For our formal definition, we define $O(g(n))$ as a set of functions and a function $f(n)$ can be a member of this set if it satisfies the following conditions:

$0$ ≤ $f(n)$ ≤ $cg(n)0$ ≤ $f(n)$ ≤ $cg(n)$

constant c is a positive constant and the inequality holds after input size n crosses a positive threshold $n0$

If an algorithm performs a computation on each item in an array of size n, we can say the algorithm runs in $O(n)$ time (or it has constant time complexity) and performs $O(1)$ work for each item.

What is space complexity and time complexity?

The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Similarly, the Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

Both depend on several external factors such as computer hardware, operating system, etc, but none of these factors are considered when running an analysis on the algorithm.

Here’s some common complexities you’ll find for algorithms:

• Quadratic time: $O(n^2)$

• Linear time: $O(n)$

• Logarithmic time: $O(n log n)$

• Exponential time: $2 ^{polyn}$

• Factorial time: $O(n!)$

• Polynomial time: $2^{O(log n)}$

Big O Notation for data structures

Big O Notation for sorting algorithms

Note: even though the worst-case quicksort performance is quadratic($O(n2)$) but in practice, quicksort is often used for sorting since its average case is logarithmic ($O(n log n)$).

Wrapping up and next steps

Now that you’ve gotten a handle on the common topics in Big O, you should be suitably prepared to tackle most questions you come across. There are other more technical topics that we didn’t cover such as,

• Complexity Theory
• Big Theta notation
• Lower Bounds Analysis
• Probabilistic Analysis
• Amortized Analysis
• Recursion

If you’d like to learn these topics, check out Educative’s course, Big-O Notation For Coding Interviews and Beyond. The course explains the concepts in layman’s terms and teaches how to reason about the complexity of algorithms without requiring you to have an extensive mathematical skillset. By the end, you’ll be able to face any Big-O interview question with confidence.

Happy Learning!

Continue reading about algorithm optimization

• The insider’s guide to algorithm interview questions
• Big O Notation: A primer for beginning devs
• Dynamic Programming Tutorial: making efficient programs in Python