Time Complexity of Algorithms Explained with Examples

There are indeed multiple ways of solving any problem that we might face, but the question comes down to which one among them is the best and should be chosen. But let’s focus only on algorithms, the best way to find the right solution for a specific problem is by comparing the performances of each available solution. Here Time complexity of algorithms plays a crucial role with Space Complexity as well, but let’s keep it for some other time.

In this blog, we will see what is time complexity, how to calculate it, and how many common types of time complexities are there.

Let’s begin…

Index

1. What is Time Complexity
2. Big O Notation
3. How to calculate Time Complexity
4. Short Hand Rule to calculate Time complexity — Drop the constants and Remove all non-dominant terms
5. Example Time
6. Types of Time Complexities — Constant, Linear, Quadratic, Polynomial, Logarithmic, linaerithmic and Exponential, Time Complexity.
7. Conclusion
8. FAQ’s

What is Time Complexity of algorithms?

Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input. Here, the length of input indicates the number of operations to be performed by the algorithm.

It depends on lots of things like hardware, operating system, processors, etc, and not just on the length of the input. However, we don’t consider any of these factors while analyzing the algorithm. We will only consider the execution time of an algorithm.

From this, we can conclude that if we had an algorithm with a fixed length or size of the input, the time taken by that algorithm will always remain the same.

Let’s take an example to understand this better -

The above statement is only printed once as no input value was provided (number of times it should run), thus the time taken by the algorithm is constant.

But for the above code, the time taken by the algorithm will not be constant as the above code contains a ‘for loop’ iterating the algorithm equal to the size of the input. In the above code, the size of the input is taken as 5, thus the algorithm is executed 5 times.

From this, we can conclude that if the statement of an algorithm has only been executed once, the time taken will always remain constant, but if the statement is in a for loop, the time taken by an algorithm to execute the statement increases as the size of the input increases.

But if the algorithm contains nested loops or a combination of both, a single executed statement and a loop statement, the time is taken by the algorithm will increase according to the number of times each statement is executed as shown

From this, we can draw a graph between the size of the input and the number of operations performed by the algorithm which will give us a clear picture of different types of algorithms and the time taken by them or the number of operations performed by that algorithm of the given size of the input.

From the above graph, we can say that there exists a relationship between the size of the input and the number of operations performed by an algorithm, and this relation is known as the order of growth and is denoted by Big Oh (O) notation which is an asymptotic notation.

Big O Notation

It is used to express the upper limit of an algorithm’s running time, or we can also say that it tells us the maximum time an algorithm will take to execute completely. It is also used to determine the worst-case scenario of an algorithm.

Asymptotic Notation is used to describe the running time of an algorithm with a given input. There are mainly three types of asymptotic notations -
Big Oh (O) — used to calculate the maximum time taken by an algorithm to execute completely.
Big Theta (Θ) — used to calculate the average time taken by an algorithm to execute completely.
Big Omega (Ω) — used to calculate the minimum time taken by an algorithm to execute completely.

Continue Reading.