Big O notation is one of the most fundamental tools for computer scientists to analyze the time and space complexity of an algorithm.
Your choice of algorithm and data structure starts to matter when you’re tasked with writing software with strict SLAs (service level agreements) or for millions of users.
Big O Notation allows you to compare the efficiency of different algorithms, so when it comes to writing software, you can build a well designed and thought out application that will scale and perform better than competitors.
Here’s what will be covered:
- What is Big O Notation?
- What are time and space complexity?
- Common varieties of Big O Notation
- Asymptotic analysis: How to find the complexity of an algorithm
- Big O Notation examples
- Big O Notation cheat sheet
Get hands-on practice with Big O
Be confident in any coding interview with dozens of practice interview questions.
Big-O Notation For Coding Interviews and Beyond
What is Big O Notation?
Big O Notation is a mathematical function used in computer science to describe how complex an algorithm is — or more specifically, the execution time required by an algorithm. In software engineering, it’s used to compare the efficiency of different approaches to a problem.
With Big O Notation, you express the runtime in terms of how quickly it grows relative to the input, as the input gets arbitrarily large. Essentially, it’s a way to draw insights into how scalable an algorithm is.
It doesn’t tell you how fast or how slow an algorithm will go, but instead about how it changes with respect to its input size.
What are time and space complexity?
When talking about Big O Notation it’s important that you understand the concepts of time and space complexity, mainly because Big O Notation is a way to classify complexities.
Complexity is an approximate measure of the efficiency of an algorithm and is associated with every algorithm you write. This is something that all programmers must be aware of.
There are two kinds of complexities: time and space. Time complexity and space complexity are essentially approximations of how much time and how much space an algorithm will take to process certain inputs respectively.
Typically, there are three tiers to solve for (best case, average case, and worst case) which are known as asymptotic notations. These notations allow us to answer questions such as:
- Does the algorithm suddenly become incredibly slow when the input size grows?
- Does it mostly maintain its quick run time as the input size increases?
Best case — represented as Big Omega or Ω(n)
- Big-Omega, commonly written as Ω, is an Asymptotic Notation for the best case, or a floor growth rate for a given function. It provides us with an asymptotic lower bound for the growth rate of the runtime of an algorithm.
Average case — represented as Big Theta or Θ(n)
- Theta, commonly written as Θ, is an Asymptotic Notation to denote the asymptotically tight bound on the growth rate of runtime of an algorithm.
Worst case — represented as Big O Notation or O(n)
- Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or ceiling of growth for a given function. It provides us with an asymptotic upper bound for the growth rate of the runtime of an algorithm.
Developers typically solve for the worst case scenario, Big O, because you’re not expecting your algorithm to run in the best or even average cases. It allows you to make analytical statements such as, “well, in the worst case scenario, my algorithm will scale this quickly”.
Common varieties of Big O Notation
These varieties of Big-O Notation aren’t the only ones, but they’re the ones you’re most likely to encounter.
O(1) - Constant time complexity
This translates to a constant runtime, meaning, regardless of the size of the input, the algorithm will have the same runtime.
