Big O notation (sometimes called Big omega) is one of the most fundamental tools for programmers to analyze the time and space complexity of an algorithm. Big O notation is an asymptotic notation to measure the upper bound performance of an algorithm.
Your choice of algorithm and data structure matters when you write software with strict SLAs or large programs. Big O Notation allows you to compare algorithm performance to find the best for your given situation. The Big O rating helps to ensure you have a lower running time than competitors.
This article aims to provide quick answers about common questions on Big O notation you might have or you might face in an interview.
Let’s get started!
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
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 our formal definition, we define as a set of functions and a function can be a member of this set if it satisfies the following conditions:
≤ ≤ ≤ ≤
cis a positive constant and the inequality holds after input size
ncrosses a positive threshold
If an algorithm performs a computation on each item in an array of size n, we can say the algorithm runs in time (or it has constant time complexity) and performs work for each item.
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.
Here’s some common complexities you’ll find for algorithms:
What are functions?
A function is a routine that accepts an input and returns an output. It is expressed as , where the output is defined in terms of the input
|Sorting Algorithm||Worst-case scenario||Average Case||Best-case scenario|
Note: even though the worst-case quicksort performance is quadratic() but in practice, quicksort is often used for sorting since its average case is logarithmic ().
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,
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.
Join a community of 500,000 monthly readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.