Inroduction to Time Complexity

Why did the algorithm go to therapy? It had an issue with time, and needed a safe space to sort it out!

If I ask you, how time-efficient is this code you've written? What do you think will be the right way to measure it?

What if you try and run it on your machine and then tell me that it takes 18 seconds to run, so the time complexity is 18 seconds? Unfortunately, it's not a very nice way to measure the efficiency because the execution time will be different for different:

1. Devices
2. Programming Languages
3. Set of Inputs

and so on...

What's a nice way, then?

The right way is to calculate the time complexity based on the number of steps to be done by the code for a given input.

Time complexity is a measure of how the running time of an algorithm grows as the size of the input increases.

Let's take a trivial example where I give you the value of a variable N and ask you to calculate 1 + 2 + 3 ...... + N.

One of the ways, of course, is to iterate over 1, 2, 3, ..... to N and keep adding them to get the answer, i.e. you do N iterations in the code.

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int N; cin >> N;
	int ans = 0;
	for(int i = 1; i <= N; ++i)
	    ans += i;
	cout << ans << '\n';
}

Logically, I hope you'll be able to identify that, in this case, the time taken by the code will be approximately proportional to the value of N. So, this algorithm is said to have an O(N) time complexity. (also called linear time complexity)

Another way could be using that formula we all studied in school:

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int N; cin >> N;
	int ans = N*(N+1)/2;
	cout << ans << '\n';
}

Now, using the formula will lead to making the speed of code to be almost independent of the input value of N. I mean, the multiplication and division might depend a little bit on how significant the value of N is, but to a very small extent.

This algorithm is said to have an O(1) time complexity. (also called constant time complexity)

Conclusion

I hope the basic meaning of time complexity and its importance is clear. In the coming articles, we'll see different notations of time complexity and its exact relation with the runtime of a program, do some practice and read a little bit about space complexity.

So, sit tight and enjoy!