What is Big-O Notation?
Big-O Notation is a metric we use to judge the growth rate of an algorithm’s running time as we increase the input size. This is called time complexity.We might also care about the amount of memory an algorithm requires, or about the stack space when making recursive calls. This is called space complexity, and it is also described by Big-O.
However, most often we are interested in the time complexity of an algorithm, and that’s what I will resort to in my further analysis.
Asymptotic time
When it comes to time complexity, Big-O time is very often referred to as the asymptotic runtime of an algorithm. So what does that mean? This is very important and I want to talk about this before anything else.
Asymptotic complexity expresses an algorithm’s growth using the dominant terms. To understand this, consider an example:
We have two algorithms, let’s call them algorithm A and algorithm B, with runtimes of O(n) and O(2n) respectively. Which of the two is asymptotically more efficient?
You might argue that algorithm A is more efficient since n is less than 2n. However, that’s incorrect. The truth is that they are equally efficient asymptotically.
That is because the only dominant term is n. Once n becomes large enough, it will dominate the growth rate of the algorithm, making the 2 irrelevant. We can conclude two important facts from this:
Asymptotic complexity expresses an algorithm’s growth using the dominant terms. To understand this, consider an example:
We have two algorithms, let’s call them algorithm A and algorithm B, with runtimes of O(n) and O(2n) respectively. Which of the two is asymptotically more efficient?
You might argue that algorithm A is more efficient since n is less than 2n. However, that’s incorrect. The truth is that they are equally efficient asymptotically.
That is because the only dominant term is n. Once n becomes large enough, it will dominate the growth rate of the algorithm, making the 2 irrelevant. We can conclude two important facts from this:
- When calculating asymptotic efficiency, constant factors and non-dominant terms can be dropped, since they don’t make a difference to the long-term growth rate of the algorithm. In the above example, multiplying n by the constant 2 only increases the runtime by that constant factor. The algorithm will still grow linearly. The same is true for runtimes like O(n² + n), where the only dominant term is n², so it becomes O(n²).
- Asymptotic efficiency does not care about how long an algorithm takes to run. It cares about how an algorithm scales. Certainly, algorithm B would take longer to run, but the overall growth rate would be just the same as for algorithm A.
Big-O, Big-θ, and Big-Ω
I hope all makes sense so far because I want to confuse you some more.
We can differentiate between three types of notation. They are Big-O, Big-Ω (Big-Omega), and Big-θ (Big-Theta). For each, I will start with its formal definition after which we shall examine what they mean in practice.
Big-O gives an asymptotic upper bound on a function.
The formal definition is as follows:
So what does this mean? This might be an oversimplification, but to explain the above in a simple sentence we could say that Big-O means that the function’s growth rate will never be worse than this.
Now a practical example: Below we will write our first algorithm, insertion sort, which (spoiler alert) has a running time of O(n²).
This also means that it has a running time of O(n³), O(n⁴), etc. because it will never be worse than these.
As you can see in Figure 1, the value of f(n) always lies on or below c*g(n).
We can differentiate between three types of notation. They are Big-O, Big-Ω (Big-Omega), and Big-θ (Big-Theta). For each, I will start with its formal definition after which we shall examine what they mean in practice.
Big-O
Big-O gives an asymptotic upper bound on a function.
The formal definition is as follows:
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = { f(n): there exists positive constants c and nâ‚’ such that 0 ≤ f(n) ≤ c * g(n) for all n ≥ nâ‚’ }
So what does this mean? This might be an oversimplification, but to explain the above in a simple sentence we could say that Big-O means that the function’s growth rate will never be worse than this.
Now a practical example: Below we will write our first algorithm, insertion sort, which (spoiler alert) has a running time of O(n²).
This also means that it has a running time of O(n³), O(n⁴), etc. because it will never be worse than these.
As you can see in Figure 1, the value of f(n) always lies on or below c*g(n).
Big-Ω (Big-Omega):
Big-Ω gives an asymptotic lower bound on a function.
The formal definition is as follows:
Reversing the logic we took with Big-O, we can say that with Big-Ω we mean that the function’s running time will never be better than this.
Insertion sort will have a best-case running time of Ω(n) when the array is already sorted. Writing Ω(log n) and Ω(1) is also correct since the algorithm will never be as fast as this.
As you can see in Figure 1, the value of f(n) always lies on or above c*g(n).
The formal definition is as follows:
For a given function g(n), we denote by Ω(g(n)) the set of functions:
Ω(g(n)) = { f(n): there exist positive constants c and nâ‚’ such that 0 ≤ c*g(n) ≤ f(n) for all n ≥ nâ‚’ }
Reversing the logic we took with Big-O, we can say that with Big-Ω we mean that the function’s running time will never be better than this.
Insertion sort will have a best-case running time of Ω(n) when the array is already sorted. Writing Ω(log n) and Ω(1) is also correct since the algorithm will never be as fast as this.
As you can see in Figure 1, the value of f(n) always lies on or above c*g(n).
Big-θ (Big-Theta):
Big-θ gives an asymptotically tight bound on a function.
The formal definition is as follows:
The formal definition is as follows:
For a given function g(n), we denote by θ(g(n)) the set of functions:
θ(g(n)) = {f(n): there exists positive constants c₁, c₂ and nâ‚’ such that 0 ≤ c₁*g(n) ≤ f(n) ≤ c₂*g(n) for all n ≥ nâ‚’ }
To put it simply, Big-θ means a runtime that’s both O and Ω.
As we saw, insertion sort is both O(n²) and Ω(n) so consequently, it is θ(n²).
As we saw, insertion sort is both O(n²) and Ω(n) so consequently, it is θ(n²).
“In industry (and therefore in interviews), people seem to have merged θ and O together. Industry’s meaning of big O is closer to what academics mean by θ, in that it would be seen as incorrect to describe printing an array as O(n²). Industry would just say this is O(n).” — Cracking the Coding Interview: Gayle Laakman McDowell
You can see in Figure 3 what an asymptotically tight bound looks like. The value of f(n) always falls between c₁*g(n) and c₂*g(n) inclusive.
The most common runtimes
Before we dive into code let’s review some of the most common runtimes you will encounter.
O(1): This is called constant time. No matter the size of n, the operation will always take the same amount of time to perform. This is the best time complexity you can have, but it’s also very rare.
O(log n): This is called logarithmic time. O(log n) is still a fairly efficient runtime. An example of an O(log n) time algorithm is binary search.
O(n): This is called linear time. The running time increases at most linearly with the size of the input. An algorithm that prints all the values in an array has O(n) time since the time it requires is proportional to the size of n.
O(n log n): This is called linearithmic time. Two examples for this runtime are merge sort and heapsort.
O(n²): This is called quadratic time. This is often considered a very bad runtime. An example is insertion sort.
O(1): This is called constant time. No matter the size of n, the operation will always take the same amount of time to perform. This is the best time complexity you can have, but it’s also very rare.
O(log n): This is called logarithmic time. O(log n) is still a fairly efficient runtime. An example of an O(log n) time algorithm is binary search.
O(n): This is called linear time. The running time increases at most linearly with the size of the input. An algorithm that prints all the values in an array has O(n) time since the time it requires is proportional to the size of n.
O(n log n): This is called linearithmic time. Two examples for this runtime are merge sort and heapsort.
O(n²): This is called quadratic time. This is often considered a very bad runtime. An example is insertion sort.
A practical example
This is all good, but now you might be wondering about what practical use all of this has when it comes to the daily grind of building iOS apps. Indeed, you can build apps without knowing all this.
However, before concluding this article I wanted to present one practical example where knowledge of this type comes in quite handy.
Consider you have to check whether an element is contained in a collection of a really large pool of elements. (A quite imaginable scenario if you’re working for a large company.)
Without going into the details, which could serve as a separate article on their own, let’s just say that it matters a great deal whether the collection in which you have to test for membership is an Array or a Set.
A Set is implemented with a hash table, and it’s essentially a dictionary that only stores keys. Looking up a value takes constant time.
Contrast this with looking up a value in an array, which takes linear time.
So you have O(1) vs. O(n). If, for example, you have to find a certain user among a collection of 1 million users, the difference between the two runtimes becomes quite substantial.
However, before concluding this article I wanted to present one practical example where knowledge of this type comes in quite handy.
Consider you have to check whether an element is contained in a collection of a really large pool of elements. (A quite imaginable scenario if you’re working for a large company.)
Without going into the details, which could serve as a separate article on their own, let’s just say that it matters a great deal whether the collection in which you have to test for membership is an Array or a Set.
A Set is implemented with a hash table, and it’s essentially a dictionary that only stores keys. Looking up a value takes constant time.
Contrast this with looking up a value in an array, which takes linear time.
So you have O(1) vs. O(n). If, for example, you have to find a certain user among a collection of 1 million users, the difference between the two runtimes becomes quite substantial.
Nice
ReplyDeletethanks bro
Delete