Master the Big O and Time complexity in Data structure and Algorithm
Before we jump on the Big O, Time complexity, and other jargons I want to take your few seconds and say have patience while reading this one, do not hurry and I promise you will never search for any other resources on Big O and Time complexity. So Let’s Begin!
What does good code mean?
Everyone wants to hire a good programmer who writes code. So what good code is and how do we know we are writing good code? well, the answer is simple. Good code has two important characteristics:
1. Readable:
In short, the code you write should be readable which means if your co-worker gives a look at it then he should be able to understand what is going on. Basics rules to make your code readable is by using a better variable name, a better function name, and so on.
2. Scalable:
In simple terms, the codebase you have written should not decrease it’s performance or should not slowdown if the user of your website or app increases over some period of time. You might be saying but how can we write a code which isn’t going to slow down in the future and how can we understand which code is going to perform well and which one is going to slow down when user/input increases? And your answer is Big O. It helps you to measure the performance of your code.
Big O and scalability tells you how much does the Alogorithm slowdown when we grow bigger and bigger with our input/user.
Before diving deep into Big O. Let me show you an interesting example.
const fruits = ['mango', 'apple', 'orange', 'banana', 'grapes'];
function searchApple(array) {
let timeStart = performance.now();
for (let i=0; i<array.length; i++) {
if(array[i] === 'apple') {
console.log("FOUND APPLE");
}
}
let timeEnd = performance.now();
console.log('Time taken: ' + (timeEnd - timeStart));
// (timeEnd - timeStart) gives you the total execution time
}
searchApple(fruits);OUTPUT
FOUND APPLE
Time taken: 0.100000047
So in the ‘searchApple()’ function, we tried searching apple from the ‘fruits’ array and calculated the total time taken to search apple by ‘searchAppple()’ function using performance.now() (timeEnd — timeStart). And in my pc it took 0.100000047 milliseconds.
you can try running it in your pc and you might get different execution time depending on your pc processor.
Now Let us assign more inputs to the ‘searchApple()’ function. Look at the code carefully.
const Hugefruits = new Array(1000000).fill('apple');
// creating an array with 1000000 apple in it
function searchApple(array) {
let timeStart = performance.now();
for (let i=0; i<array.length; i++) {
if(array[i] === 'apple') {
console.log("FOUND APPLE");
}
}
let timeEnd = performance.now();
console.log('Time taken: ' + (timeEnd - timeStart));
// (timeEnd - timeStart) gives you the total execution time
}
searchApple(Hugefruits);OUTPUT
FOUND APPLE
FOUND APPLE
FOUND APPLE
.
.
.
.
.
Time taken: 343.1999999
It took 343.1999999 milliseconds. As the input grew, our ‘searchApple()’ function becomes slower and slower.
Problem with Time based approach:
The problem with our above approach is we use execution time to determine the performance of our code. But you might notice by now that execution time depends on the processing power of the pc. So it might be faster on your computer and you might send it to your friend and say oh boy! i wrote an awesome code. And your friend (having relatively slower processor on his/her pc) while running your code might see taking much more execution time and start judging on your skills. you poor Guy!
What is the solution?
Instead of checking ‘execution time’ to measure the performance of code. We can just calculate the number of operations present in the code and find which is better. And here, Big O help us to measure code performace by counting number of operations.
How Big O measures the performance of code?
We already discussed, Big O help us to determine how will our code performance be impacted as our input grows larger and larger. Looking at the above example, when we gave ‘fruits’(const fruits = [‘mango’, ‘apple’, ‘orange’, ‘banana’, ‘grapes’]) array to ‘searchApple’ function less operation was required to execute it. But when we gave ‘Hugefruits’(const Hugefruits = new Array(1000000).fill(‘apple’)) array, the number of operation increased resulting in slowing the code performance.
Not all function executes same number of operations as input grow larger. Some function starts executing huge number of operation for x input size while some doesn’t increased much operations. So for different functions we have different Big O Time complexity notation like O(1), O(logn), O(n), O(nlogn) etc.
O(1) Constant Time
Let’s take an example to understand constant time complexity
const fruits = ['mango', 'apple', 'orange', 'banana', 'grapes'];
function printFirstFruit(fruits) {
console.log(fruits[0]); // 1 operation
}
OUTPUT
mangoIn this function, only operation was needed to print first value. So the Time complexity of ‘printFirstFruit()’ function will be O(1) (pronounced as ‘order of one’). Let’s go to another example.
const fruits = ['mango', 'apple', 'orange', 'banana', 'grapes'];
function printTwoFruits() {
console.log(fruits[0]); // 1 operation
console.log(fruits[1]); // 1 operation
}
OUTPUT
mango
appleIn ‘printTwoFruits()’ function, two operation was needed two print the values. So the Time complexity is O(2).
In both cases we got some constant number of operation to performed. So we call them constant Time complexity.
O(n) Linear Time
It means as the number of input grows, the number of operations will grow linearly.
const fruits = ['mango', 'apple', 'orange', 'banana', 'grapes'];
function searchApple(array) {
for (let i=0; i<array.length; i++) {
if(array[i] === 'apple') {
console.log("FOUND APPLE");
}
}
}
searchApple(fruits);OUTPUT
FOUND APPLE
Another one
const Hugefruits = new Array(1000000).fill('apple');
function searchApple(array) {
let timeStart = performance.now();
for (let i=0; i<array.length; i++) {
if(array[i] === 'apple') {
console.log("FOUND APPLE");
}
}
}
searchApple(Hugefruits);OUTPUT
FOUND APPLE
FOUND APPLE
FOUND APPLE
.
.
.
.
We can clearly see in both the examples the number of operation starts growing with the increase in number of input size. This type of complexity is called O(n) or Linear time complexity.
