In this article, we will learn about what is time and space complexity of an algorithm. In the previous article, I mentioned there are multiple ways to solve one problem.
For instance, there are multiple algorithms to sort a list of numbers
Now if that is the case, how do we analyse which one of them is the most efficient algorithm.
How to analyse algorithm?
If I can run 100 meters in 12 seconds, I'm faster than someone who takes 15 seconds
Analysing algorithms, however is slightly different. The absolute running time of an algorithm cannot be predicted since it depends on a number of factors
1. It can change based on the programming language used to implement the algorithm
2. The computer which the program runs on
3. Other programs running at the same time
4. The quality of the operating system and many other factors
Keeping these points in mind, we evaluate the performance of an algorithm in terms of its input size.
Types of evaluation
2. Second, we have space complexity which is the 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 a small input size but slower for a larger input size. we would never be able to accurately judge which is more efficient.
Keep in mind, there is no one solution that works best every single time, it is always good to know multiple ways to solve the same problem and use the best solution given your constraints.
If your app needs to be very quick and has plenty of memory to work with, you don't have to worry about space complexity.
On the other hand if you have little memory to work with, you should pick a solution that is relatively slower but needs less space
All right, now that we have an idea of what time and space complexity are, the next question you might have is how do we represent the time and space complexity of an algorithm?
How to represent complexity?
Well, we do that using asymptotic notations
Asymptotic notations are mathematical tools to represent time and space complexity
There are mainly three asymptotic notations
1. Big-O notation for worst case complexity
2. Omega for best case complexity and
3. Theta for average case complexity
Now at this point, if I were to explain their theoretical definitions it would unnecessarily confuse you. Instead I want to make this more practical and easier to understand as a beginner.
Once you get a fundamental understanding of these concepts, you can then on your own time refer to articles that dive deeper.
Now the first step in being practical is to not worry about the best and average case complexity, as you deal with problems you'll realise that we are primarily concerned with the worst case scenario of an algorithm and to be honest it is what is asked during interviews as well
You're more likely to be asked, can you tell me the Big-O or the worst case complexity of the algorithm you've just written and for that reason our focus as well will be on the worst case complexity in this course.
So in the next article, let's learn about the Big-O notation.
0 Comments