Prologue: A food delivery disaster
Imagine you are creating the latest food delivery service that will beat Uber Eats and all of its competitors in no time, using delivery robots. Trying to maximize the usage of your delivery agents and reduce cost, you've assigned robots to specific restaurants that have high volume of orders. Having your agent do multiple deliveries at once, you want to calculate what is the shortest possible route that visits each client and returns to the store for more deliveries or to be recharged.
You've implemented a solution that returns the exact shortest path and deploys it to find that it's too slow so servers are starting to stall. As your application is deployed in the cloud you promptly increase the number of instances to guarantee smooth deliveries just to see that the predicted costs for this month are increasing 10 fold.
You look further into the problem and even hire a senior engineer. That's when you learn this is not trivial and there is a name for this problem: Travelling Salesman Problem (TPS). There are exact algorithms for TPS, but all of them take years of computing, or an insurmountable amount of resources depending on the number of clients you need your robot to visit.
What is Algorithm Analysis
Algorithm analysis could be defined in short as a way to predict the amount of resources an algorithm might require to return the expected output.
In our food delivery example, being able to do proper algorithm analysis could have saved you a lot of trouble and money before you even started implementing your solution.
Algorithm analysis is a topic of utmost importance in the software engineering area, however it is often overlooked, especially with nowadays mentality of "just throw more memory and CPUs/GPUs" that relatively cheap hardware and cloud computing has pushed or at least facilitated.
What should we look at when analyzing an algorith?
When analyzing an algorithm, you could focus on different resources:
- Network Bandwidth
- Computational time
However most resources on algorithm analysis, as well as this series of articles, will focus mainly on computational time and secondarily on memory usage.
Tip: Check your cloud provider bill and see where is the bottleneck you need to improve
Does the same analysis work for all different platforms out there?
Different platforms will have marginally different results, however as long as the computation paradigm is the same the results should be similar.
What can affect the performance of my algorithm?
Depending on the algorithm, various factors may affect its computational time (also called running time) for example, a sorting algorithm might be affected by the input size and the input element order.
How to define the input size?
The best notion for input size depends on the problem being studied. For many problems, such as sorting, the most natural measure is the number of items in the input. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. If the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph.
The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed.
Ok, but what is really the running time?
The running time of an algorithm is the number of operations or “steps” executed. To define what a "step" means, let's assume a constant amount of time is required to execute each line of our code. One line may take a different amount of time than another line, but we shall assume that each execution of the ith line takes time t, where t is constant.
In the next article of this series we will go over the actual way to analyze an algorithm using one of the most basic sorting algorithms, Bubble Sort.
Credits: This series of articles is heavily based on my favorite books on the topic
- Introduction to algorithms / Thomas H. Cormen et al, —3rd ed.
- Algorithms / Robert Sedgewick, Kevin Wayne, -4td ed.
- The Algorithm Design Manual / Steven Skiena, -3rd ed.