Big-O Notation for beginners
We call the term “Big-O” in algorithms when we want to calculate space complexity and time complexity. Here, time complexity refers to an “amount of time taken by an algorithm to run” and space complexity as “amount of resources, usually space or memory, taken by an algorithm to run”. Because we always want to choose the best solution that require less time and space complexity, using Big-O calculations allows us to choose the most efficient solution among multiple ones. This blog will cover time complexity rather than space complexity for the time being.
First, it is important to note that Big-O is a function which determines portion of time and space depending on the size of algorithm as its input. It denotes how long an algorithm will take to execute. Big-O Notation is represented as a function: O(f(n))
Common types of Big-O notations are:
- O(1) — Constant time complexity
- O(n) — Linear time complexity
- O(n²) — Quadratic time complexity
- O(log n) — Logarithmic complexity
Every line of code is a cost to the system, meaning resources such as CPU, memory, and network that computers have to use in order to execute. In terms of CPU usage, we measure the cost as time complexity and memory usage as space complexity. To elaborate more on time complexity, every operation takes time — operations could be simple statement, complex mathematical operation, assignments, or conditional statements. And simply put, finding the maximum number of an array of 5 elements is, of course, faster than finding the maximum number of an array of 100 elements. Thus, the more operations there are, the more time computers will take to execute every operation.
Constant time — O(1)
Execution time of constant time algorithm is independent of the size of input and will always take constant time for execution. Examples include:
Linear time — O(n)
Execution time of linear time algorithm is proportional to the input size (n). Examples include: traversing an array, a linked list; linear search; comparison of two strings, palindrome check, bucket sort, and etc. Here is a good example:
Within the for-loop, each statement has a complexity of O(1). Since there are 3 statements in the loop, the total complexity of logic within for-loop would be O(1+1+1) = O(3). Now, note that the loop runs n times with every i-th iteration of the array taking O(3). Therefore, total complexity of this entire code would be O(3 * n) = O(3n) = O(n). Constants are generally ignored, for as the value n increases, 3 becomes negligible.
Quadratic time — O(n²)
Execution time of quadratic time algorithm is proportional to the input size (n²). Examples include nested loop, bubble sort, insertion sort, selection sort, and etc. Here is a good example:
We already know that complexity of inner loop (j index) is O(n) from the example of linear time complexity. Also, time complexity of outer loop (i index) is O(n), so in total, this nested loop will have O(n * n) = O (n²) complexity. Constants are also ignored.
Logarithmic complexity — O(log n)
Execution time of logarithmic time algorithm is proportional to the input size (log n). Examples include simplified loop version of binary search algorithm.
Here, the loop starts with index of n and i decreases by dividing 2. So, the total complexity would be:
with some constant k representing number of iterations. This then could be simplified by:
Therefore, the total complexity of the loop would be O(log n). I would highly recommend taking a look at binary search algorithm, which is a great representation of algorithm with O(log n) complexity.
This is the cheat sheet for common data structure operations.
I hope this blog gave you a clear vision of what Big-O notations are in general. I would also highly recommend checking out http://bigocheatsheet.com/ for Big-O Notations. There are also other notations widely used such as O(n log n), O(n³), O(2^n) and etc. I would recommend looking up those too. Thank you.
Resources
https://medium.com/@cindychen13.work/a-beginners-guide-to-big-o-notation-793d654973d