While learning Data Structures & Algorithms, you must have come across the term 'Complexity Analysis' a lot. But what does it mean? And how does it works?
Keep reading & all your questions will be answered...
In simple terms, an algorithm is just a series of steps to solve a particular problem. An algorithm takes an input and gives some output.
Now it is possible that a problem may have multiple solutions & we can design multiple algorithms to get different solutions.
Now the question comes in mind that which solution is the most efficient one? One way to answer it is to compare different algorithms with one another and see which one performs the best.
Now, this is not as easy as it sounds...
Consider this, suppose you have a brand new & super-powerful MacBook while one of your friends has a really old & slow MacBook. Now if you try running an algorithm in both of the MacBooks, you will notice that in the new MacBook, the algorithm is executed a lot faster than the old MacBook.
So is our algorithm slow because it took a lot of time in the old MacBook? Or is it fast since it got executed pretty fast in the new MacBook?
Noticed the problem with comparing the algorithms through the traditional way?
The performance of an algorithm is dependent on several factors. And any changes to these factors may lead to different performance results.
So to tackle this issue and come up with a universal way of analyzing algorithms that remain unaffected in all, we perform Complexity Analysis.
So until now, we know that complexity analysis helps us compare algorithms and find the best one. Considering this we can also say that the best algorithm will have the best complexity.
But now what is complexity in the first place?
Well according to Wikipedia, the Complexity of an algorithm is the amount of resources required to run it
Now an algorithm may require multiple resources to learn but these resources or requirements vary from one algorithm to another. But two things that every algorithm requires to run are time & space.
Hence we calculate the complexity of an algorithm considering only these two requirements i.e. space & time.
Space refers to the amount of memory required to execute the algorithm.
Time refers to the amount of time required by the algorithm for complete execution.
An algorithm is said to have the best complexity when it can execute properly in the least amount of space and time.
Now to express complexity we have some notations but do not worry about them. We will cover it in the next part of this series.
Complexity Analysis also helps us to find the most suitable data structure for a given task. While learning data structures, we are going to talk a lot about complexity analysis.
- is a great way of comparing algorithms to find the best one
- particularly focuses on two types of complexities - Space (memory) & Time (amount of time)
- helps us find the most suitable data structure for a given task
Thank you so much for reading! I hope you learned something new today. Please leave a like, a lovely comment, or feedback & also consider following me as I regularly post useful & informative articles to help you become a better programmer.
If you like my work please consider Buying me a Coffee so that I can bring more projects, more articles for you.