Is Time Complexity Important?
In today’s fast paced world of Internet, performance is key. Instant Gratification is not only behavior but also expectation from the new age application.
Time Complexity is critical to the performance of the applications. This concept is not new but being ignored by many. In this blog, we will be discussing about the concept of time complexity.
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. It is generally defined as the number of times a statement is executed. For example
For(i=0, i<10,i++)
{
i = i+1
}
In the above example, loop runs 10 times for the value of i varying from 0–Hence the above code needs to run 10 times. This is called as
Big O Notation
Big O notation is the term similar to Kg used for weight. We use Big O Notation to define the time complexity.
Some of the common Time complexity types are below
- Linear: Where the time complexity is N. It is shown in the For loop above.
- Quadratic: Where the time complexity is N². It is true in terms of Nested Loops.
- Logarithmic: Where the time complexity is LogN. It is valid where algorithm divides the working area in half with each iteration
Our Problem
If you have 100 items in list A, and 100 items in list B, and you know that for each item in list A there’s one item in list B that matches it, and you want to produce a list of pairs.
Our Solution
We have multiple solution for the above problem.
- Nested Loop
In the above loop, for each item X , it will run for N in Y. Time Complexity of this is Quadratic (N²). That means, if we have N =1⁰⁶ then it will run 1⁰¹² times.
2) Sort Method
In the above sort method, algorithm’s time complexity is 2N & it will be much faster.
But we need to remember, that each solution may hold true in certain circumstances. But select the solution with best time complexity.
Reference:
