We’ve heard about algorithms a lot. In this short article, I am going to a little bit talk about algorithms, their importance, etc. which will be the first post in my Algorithms series. If you follow the series, you will get familiar with different type of algorithms, old and classic ones, or new and heuristic ones. Just follow the series.

What is an algorithm?

An algorithm in simple language is a finite set of instructions for calculating a function. For example we are looking for a file in a folder, what we might do is, we start from beginning of the list, check each and every file until we find the file we want or reaching to the end of the list. This is an algorithm.

Why we should learn them?

Algorithms are actually ways to solve problems; but they are not the solution. By learning algorithms you will find methods that help you in solving problems. It is like Data Structure. If we consider data structure as a tool, algorithms will be manual that helps us to learn how to use those tools to do desired task.

When shall I use specific algorithm?

The solution and algorithm you choose for any given problem, depends to:

• The way you are looking at the problem and visualizing it
• Run Time/Space limits
• Input Size

These are only key factors. There are lots of other factors that might play a key role in selecting an algorithm, such as data structure, etc. Maybe the last two factors are obvious, but let’s see how the first factor might play a key role. Consider the classic 8-Queen problem. In this problem we want to place 8 queens in a 8×8 chessboard in a way that none of them could attack others.

Let’s say we are going to solve it by placing one queen at a time in a way that it will not be able to attack previous queens we have placed. Once we reached to a place that we cannot find a place for this queen, we will return back and move the previous queen to another cell and then continue, until we reach to a result. In this way we are using backtracking to solve the issue.

But there is another way to look at the problem. Let’s say we will place 8 queens in 8 rows randomly. Then we start to move queens in a way to minimize the number of queens that can attach each other. Now we have turned the problem into optimization problem. So as you can see, they way you are understanding and visualizing a problem will play a key role in solving it and finding algorithm.

How we can compare two algorithms?

Well, if there are different algorithms to solve a problem, then there should be some ways to compare them (I’m genius). We usually compare two algorithms based on their time and space complexity. Time and space complexity are not displaying the exact amount of time/space are required to solve a problem; instead they indicate how the time/space requirements will grow when the problem size grows. Since we want to study how the time/space requirements will grow, then we don’t need to consider the exact equation of time/space complexity; We can just consider the biggest factor. Let’s see this in below simple example.

Finding an item in an ordered list

Let’s say we have an ordered list of numbers with size n and we want to see if this list contains number x or not. We can use below ways to search for x:

Algorithm 1: We will start from first item and compare it with x: if it is equal, then list contains this number, otherwise, we will go to next item until we reach end of the list or find x in the list.

Algorithm 2 (Binary Search): We compare x with the middle item of the list. If x is larger than middle item, then we should be able to find it in the second half of the list and we can ignore the first one and vice versa. Once we find out on which part of the list we have to search for x, then we repeat the same step, compare x with the middle item of this new list (first/second half). We continue this until we find x or reaching to a list with size 1.

As you can see, we usually using second algorithm to find items in ordered list. Now let’s see how we can compare the time complexity of these two algorithms. When we want to estimate time complexity, we count how many times a key action or block of actions will be repeated. Like in our example, how many times we should perform comparison to find out given list contains x or not. In order to eliminate role of x in our estimation, we consider the worth-case scenario such as list does not contain x.

In the algorithm 1, we need to do comparison n times in the worth-case (which is obvious). But what about algorithm 2? The answer is log n (when we are using log, we usually mean log in base 2). If you check the algorithm, you will see at each step we will divide list into half, so the list size will change like: n, n/2, n/4, n/8, n/16, … . So in the worth-case we will continue up to log n. When we want to denote the time/space complexity, we usually use big O, and we will show it as O(n) or O(log n). This mean we are just considering the most significant factor and we are neglecting the others. For example if you algorithms time complexity is polynomial like (n²+n), then we can say the time complexity is equal to O(n²).

 Conclusion

Finding proper algorithm for a given problem could be challenging. Learning more algorithms will give us better vision and understanding, and we will be able to analyze problem from different aspects and find different algorithms to solve the problem. Time/space complexity enables us to compare algorithms and choose the best algorithm based on input size and other limitations.

This was an introduction about algorithms. In next articles we will see different type of algorithms and their pros and cons.  Also we will learn how to calculate time/space complexity and combine different algorithms with some heuristic functions in order to reduce complexity.