3 min read Algorithms

Introduction to Algorithm Analysis (1)

Introduction to Algorithm Analysis (1)
(Here is Part2 and Part3)

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.
Delivery robots from Starship Technologies

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:

  • Memory
  • 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.

Coming next...

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.

You might also like...

Apr
06
Introduction to Algorithm Analysis (5): HeapSort

Introduction to Algorithm Analysis (5): HeapSort

Last time we branched out from just algorithms and began analyzing a very simple data structure and operations on it.
9 min read
Mar
11
Introduction to Algorithm Analysis (4): Dynamic Arrays

Introduction to Algorithm Analysis (4): Dynamic Arrays

After having learned about several sorting algorithms and utilizing best-, worst- and average case analysis to gain a better understanding
7 min read
Mar
05
What is Dynamic Programming?

What is Dynamic Programming?

Introduction Dynamic Programming is a programming technique of breaking tasks into smaller tasks and storing them to avoid repeating them.
3 min read
Mar
02
Introduction to Recursion

Introduction to Recursion

What is Recursion? Introduction To understand recursion, you must first understand recursion. Software development is full of recursive jokes like
3 min read
Feb
27
Introduction to Algorithm Analysis (3): Quicksort

Introduction to Algorithm Analysis (3): Quicksort

After carefully examining BubbleSort - an algorithm with pretty much the worst possible reputation - we continue our study of famous sorting methods with an algorithm at the opposite end of the popularity spectrum.
6 min read