Table of Content
- How to Check the Performance of an Algorithm?
- Why are Algorithms Evaluated in Terms of Input Size?
- How to Determine the Time and Space Complexity of an Algorithm?
- Wrap Off
In the previous lesson, we mentioned that there are multiple ways to solve one problem.
For example, there are multiple algorithms to sort a list of numbers and some algorithms are better than others in terms of performance.
In this lesson, you will learn how to analyze which algorithm is the most efficient by checking its performance in terms of time and space complexity.
How to Check the Performance of an Algorithm?
Generally, when people talk about performance, they use an absolute measurement. For instance, if a person can run the Olympic's 100 meters in 5 seconds, they will be faster than someone who takes 10 seconds.
However, when analyzing the performance of algorithms, it is slightly different.
The absolute running time of an algorithm cannot be predicted, since it depends on a number of factors.
The performance of an algorithm varies based on the programming language used to implement the algorithm, the computer it programs runs on, the operating system and the version, and many other factors.
As a result, we evaluate the performance of an algorithm in terms of its input size.
Why are Algorithms Evaluated in Terms of Input Size?
Evaluating algorithms using the input size ensures that 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.
There are two ways that algorithms are evaluated, by their input size:
- Time Complexity: the amount of time taken by an algorithm to run as a function of input size.
- Space Complexity: the amount of memory taken by an algorithm to run as a function of input size.
It's worth knowing that 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.
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 consumes less memory.
How to Determine the Time and Space Complexity of an Algorithm?
The space and time complexity of an algorithm is determined using asymptotic notations.
Asymptotic notations are mathematical tools used to represent time and space complexity.
There are mainly three asymptotic notations:
- Big-oh notation (O): for worst-case complexity
- Omega notation (Ω): for best case complexity
- Theta notation (Θ): for average case complexity
We will not be going into their theoretical definitions, rather, we will 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.
Another thing we want to point out is that we will only focus on the worst-case complexity and not go in-depth into the best and average case complexity.
As you solve algorithmic problems, you'll realize that those problems are primarily concerned with the worst-case scenario of an algorithm.
In the next lesson, we will learn about the big-oh complexity.
Wrap Off
In this lesson, we showed you how to analyze which algorithm is the most efficient by checking its performance in terms of time and space complexity.
We also talked about how to determine the time and space complexity of an algorithm.
If you learned from this tutorial, or it helped you in any way, please consider sharing and subscribing to our newsletter.
Please share this post and for more insightful posts on business, technology, engineering, history, and marketing, subscribe to our newsletter.