Know The Time Complexity Of Your Programming Code
A walkthrough to Big-O Notation
Introduction to Data Structure:
In our day to day life, we always come to various scenarios where organized stuff makes our life easier. For example, In the case of pic A below, picking a dress will certainly take less time than finding a dress from a messy closet such as pic B.
The same rule applies in the programming world too. The data structure is a way to organize the data in your computer memory to make it easier to process and access.
Introduction to Algorithms:
To bring the red dress from the Pic A closet, in general, what would be the process that someone will follow? i) Go to the Room ii) Open the Closet iii) Search for Red dress iv) Pick the red dress. This is nothing but a set of instructions that one followed to perform the task that is getting the red dress from the closet. In a similar manner in programming as well we apply a set of instructions to perform or solve a given task. This set of instructions are nothing but the algorithms.
Types of Data Structure and Algorithms:
Various algorithms can be used to solve a given problem in various way. For example: Write a program to find the sum of first n natural numbers?
There is N number of ways, we can solve a problem, but as shown in figure 3, certain approaches become more efficient in terms of execution time or space network bandwidth taken. So choosing the right set of data structures and algorithms for the program is very much crucial.
Introduction to Big-O Notation:
Big-O is the metric used to describe the efficiency of an algorithm. The performance of a program is measured by various resources a code consumes based on the requirement of the product. There are 3 different axes based on which measure the performance.
- Time Complexity: How long your program takes to run. It deals with the amount of processing or number of operations a code has to perform to accomplish its objective
- Space Complexity: How much memory or disk space does your program occupies. This is both memories needed by code to store information at the runtime as well as disk space needed by code for persistent storage.
- Network Complexity: How much data your program does transfer over a network. The amount of network bandwidth code uses to pass information to the client or another system.
How to choose an efficient DSA?
Optimize your code based on your system requirement. Like whether it is a time-critical system or space critical system. And application should take less space in a mobile phone in that case space complexity takes priority whereas a home page needs to be up and run in very less time, in that case, time complexity takes the priority. I hope you are now aware of Big-O notation and various metrics such as time, space, network, etc.
There are again 3 different types of complexity that come to the picture such as:
i) Big O (Big O): A complexity that is going to be less than or equal to the worst time a program can take.
ii) Big Ω (Omega): It is a complexity that is going to be at least more than the best case.
iii)Big θ (Theta): It is a complexity that is within the bound of the worst and the best case.
Let’s focus on the most widely used complexity, which is Big O complexity and we will be focusing on Time complexity in this article. Big-O time complexity is various types such as:
- O(1): We can call it as Big O of one or O of one, which is a constant time complexity, where for any given input, the execution time will not change. It will remain constant regardless the increase or decrease of input data set N. Eg.: Accessing a specific index within the array always takes an O(1) time complexity.
int[] array = {1,3,5,7,9};
System.out.println(array[2]); // output: 5 ---> It doesn’t matter whether the array has 10 or 100 indexes, looking up at a specific location (here at index 2), it will take the same amount of time.2. O(N): Big O of N or O of N is a linear time complexity where time complexity will grow in a direct proportion to the size of the input data. Ex.: Traversing through all the elements in a given array.
int[] newArray = {1,3,5,7,9,4,2,0};
for(int i =0; i < newArray.lenght; i++){
System.out.println(newArray[i]); // It visits every element in the array, hence it takes linear time, which means if we have N element in the array it will take N number of time. If N increases time taken also increases and the similar way if N decreases time taken by the program as well decreases.
}3. O(log N): Big O of log N or Log O of N is a logarthimic time complexity, where the complexity proportional to the logarithmic of the input. Ex.: Finding an element in a sorted array.
int[] newArray = {1,2,3,4,5,6,7,8};
for(int i =0; i < newArray.lenght; i+3){
System.out.println(newArray[i]); // It visits only certain elements in the array,as we are doing i+3, hence this is one of the example of Logarithimic time complexity.
}4. O(N²): The time complexity of an algorithm is refered as Big O of N² or O of N² , whose performance is directly proportional to the square size of input dataset(N). Ex.: Traversing through every index in an array twice.
int[] newArray = {1,2,3,4,5,6,7,8};
for(int i=0; i < newArray.lenght; i++){
for(int j=0; j< newArray.lenght; j++){
System.out.println(newArray[i]); // Here two loops are there so j loop run once till all elements of the newArray and then again i loop loop through all the elements of newArray. The time taken here becomes the square size of total input.
}
}
}5. O(2^n): Big O of 2 to the power of N or exponential time complexity is an algorithm whose growth doubles with each addition to the input data set. Eg. Double recursion in a fibonaci series.
public int fibonacci(int N){
if(N==0 || N==1){
return N;
}
return fibonacci(N-1) + fibonacci(N-2); // Here the recursive instantiation will pass over every number from the number to zero.It will do this twice as it checks f(n-1) once and then again f(n-2) until it reaches the base case if statement i.e N becomes either 1 or 0.
}6. O(N + M): If an algorithm is in the form of “ do this first and when you are all done, do that” then you add the runtime. For ex. Loop through all the element in array A and then loop through the element in array B.
public static void withTwoLoop(int N, int M){
for(i = 0; i< N ; i++){
System.out.println(i);
}
for(j = 0; j< M; j++){
System.out.println(j); // In this program two loops are there. First loop runs N times, once it is done the second loop runs M times. Hence total time taken can be refered as (N+M) time.
}
}7. O(N * M): If an algorithm is in the form of “ do this for each time you do that” then you multiply the runtimes. For example a nested loop where for each iteration of the first loop the second loop iterates till M times.
public static void withTwoLoop(int N, int M){
for(int i = 0; i< N ; i++){
for(int j = 0; j< M; j++){
System.out.println(i*j);
} // In this program two loops are there. The difference between this and the previous program is here for each i value the j runs M time. As i runs N time, hence the total time complexity will become O(N*M).
}
}These are various Big-O time complexity that we talked so far. Have a look at below fig. 5 to know which time complexities are fasters in terms of time taken.
Rules of measuring Big O time complexity of an program:
Now let’s take an program and apply the above rules to calculate the time complexity.
This is how we can calculate the time complexity of any given problem. I hope this discussion add up to your knowledge on Data structure and Algorithms (DSA) basics, the need for DSA, various type of DSA, Big-O notations and different types of complexities, finally a thorough idea on time complexity and how to calculate time complexity of any given problem.
Thanks for reading this blog. If you enjoyed it, please give it a clap and share it. If you have any doubt or suggestions feel free to comment or send me an email. Also, feel free to follow me on, LinkedIn or Twitter.
