Time and Space Complexity

Algorithm Analysis

In the previous articles of this series, I told you that there are multiple ways to solve one problem.

Example:

There are multiple algorithms to sort a list of numbers. So, now we have to analyze which one of them is the most efficient algorithm to solve the problem.

Generally, when we talk about performance, we use an absolute measure. If I can run 100 meters in 12 seconds, I am faster than somebody who can take 15 seconds.

Analysing algorithms however is slightly different, the absolute running time of an algorithm cannot be predicted, since it depends on many factors such as

1. The programming language used to implement the algorithm

2. The computer the program runs on

3. Other programs running at the same time

4. Quality of the operating system and many other factors

Keeping the above points in mind we evaluate the performance of an algorithm in terms of its input size.

The evaluation can be solved by two types

Time Complexity:

Amount of time taken by an algorithm to run, as a function of input size

Space Complexity:

Amount of memory taken by an algorithm to run, as a function of input size

By evaluating against the input size, the analysis is not only machine-independent but the comparison is also more appropriate. Imagine if one algorithm is faster than the other for the small input size but slower for the large input size. So we will never be able to judge which is more efficient. Remember that, no solution works every single time so it is always good to know the multiple ways to solve the same problem and use the best solution to implement in solving it given your constraint.

So for instance, if your applications need to be very quick and have plenty of memory to work with, you don't have to worry about space complexity and if you have very little memory to work with, you should pick a solution that is relatively slower but needs less space.

How to represent the complexity of an Algorithm?

Asymptotic notations

A mathematical tool to represent time and space complexity.

1. Big-O Notation (0-notation) - Worst-case complexity

2. Omega Notation (Ω-notation) - Best-case complexity

3. Theta Notation (Θ-notation) - Average case complexity

Here in our series, we will only talk about the Big-O Notation because this is the only most important notation that is asked in the interview at the tech companies. The question could be "Can you tell me Big-O or the worst-case complexity of an algorithm you just have returned".

so, let's explore the Big-O notation in the next article of this series :)