Why use Algorithms? That’s actually a good question. I know many developers who code without having any knowledge about algorithms or data structures. Some of these developers even end up at the top of the company hierarchy. Then why bother? Well if you simply want to be another developer, don’t bother to learn algorithms or data structures. However, if you want to stand out as a software developer, read on. Linus Torvalds once said, “Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” In this article, we‘ll discuss the fundamentals of computer algorithms. We will also look into a very important topic called Big “O” notations. Hopefully, I want you to successfully take your first baby step into the world of algorithms! I expect you to have a basic understanding of JavaScript to understand this article.

What are algorithms?

According to Wikipedia:

“In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ ) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.”

In other words, an algorithm is a blue print, with a set of instructions that a program should follow to accomplish a specific task. For instance, the algorithm to print “Hello World” can be used to print “Hello world” programmatically.

Nothing complicated here. The complexity lies in contriving an optimal algorithm, which is either time-efficient or space efficient. To be even clearer, the algorithm we create should make the program reach completion without wasting a lot of time or space (memory). Some algorithms are meant to consume more space, but they may be more time efficient(like the merge sort algorithm) and some , may consume no space at all, but may not be very time efficient(like the bubble sort algorithm). Every algorithm will have its advantages and disadvantages. How you use your algorithm is largely dependent on the scenario.

Time/Space complexity:

Time/Space complexity is used to determine the time or space taken by a specific algorithm. We can determine the optimality of an algorithm depending on these two factors. But how would you measure this? Well we can use a timer to calculate the time taken for a program, based on an algorithm, to complete. However this may not produce accurate results all the time. Why? Because of other influencing factors such as computer speed, OS background tasks etc, your results may not be always accurate. What can be done then? Enter Big O. By using Big O notations we can understand the efficiency of an algorithm with ease. Let’s dive right in.

Big ‘O’ notation:

According to Wikipedia, the definition of Big ‘O’ is:

“In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.”

With Big O, we try to determine the efficiency of an algorithm by regarding two factors; the size/length of the input, and time/space taken by the algorithm to process the input and produce an output.

Standard Big ‘O’ notations:

We will go through some of the standard Big ‘O’ notations.

O(n):

The above code executes ‘n’ number of times(because of the for loop of course). For instance, if the length of ‘n’ is 10, the code will get executed 10 times. The time taken for the above code to complete is linear. So the Big O of the above code is O(n). O(n) literally means that the time/space taken by an algorithm is directly proportional to the length of the input(n). O(n) is one of the standard Big O notations.  JavaScript array functions like find, filter etc have a Big O of O(n). For instance the array’s filter function will have to check all the items of the array. So the bigger the array gets, the more time the filter function will require to complete.

O(n²):

Suppose there are ‘n’ numbers of boxes and each box contains ‘n’ numbers of items. How will you go through all the items? You will of course have to use a nested for loop. We will have to traverse all the boxes (n) and the items (n) inside each box. So the input of such an implementation will be ‘n’ and its output will be n² (for the sake of clarity, n(boxes)*n(items)=n²).

So the above program is not time efficient, because the time taken to complete the task is double that of the size/length. In other words, the time taken to reach completion is quadratic. Use of nested for loops must be avoided, if at all possible.

O(logn):

This is an interesting Big O notation. However in order to explain this clearly, I will have to briefly discuss the Binary search algorithm.  First of all a binary search algorithm can only work on a sorted array. The binary search algorithm:

Steps:

1)The binary search initially looks for the middle most index of the array and compares it with the value being searched for.

2)If the value being searched for matches the value of the middle index, the code will stop its search. If not, the code will check if the value being searched for is less than the value of the middle index.

3)If it’s lesser, the code will once again find the middle index, by regarding the index before the current middle index as the last index of the array.

4)If it’s higher, the code will find the middle index, by regarding the index after the current middle index as the first index of the array. These steps will be repeated, until the code finds the value. 

This may not be very clear to you now. I will later include an exclusive article about binary search. In short, the binary search chops down the length of the array into half, after every iteration. So let’s just assume that the binary search locates the value being searched, during the last iteration and let’s also assume the size of the array to be 32. We can now equate that to,

25=32 -where 5 denotes the number of steps required to find the value, and 2 represents the chop that happens after every iteration

So generally speaking that is equal to

2x=n

By applying the rules of binary logarithm this is equal to,

log2n=x

i.e.,logn=x  -this literally means that the algorithm will require a maximum of x steps to complete

What all this literally means is that the time taken to complete is logarithmic. Hence the Big O notation for this algorithm is O(logn). This is actually very good and way better than O (n). So in order to find an element in the array below,

let a=[1,2,3,4]

it will just take the binary search two steps tops. How? Just apply the formula above. The length of the array, ‘a’, is 4 and when you apply that to the formula we get two.

log24=2

It’s as simple as that. You will understand this even better, when you fully understand the binary search algorithm. So here the algorithm is not finding the required value by comparing the value with all the values of the array. Instead it simply reduces the search scope, until it finds the value.

O(1):

This notation literally means constant time. The algorithm, based on this notation, will always take the same amount of time to complete. Consider,

The above code will print all the numbers from 1 to 5. No matter how many times you execute this code, it will take the same amount of time to complete. So the time taken to reach completion is constant. There is also another scenario we should consider. Let’s just say that we are trying to locate an element of an array ,with the array’s filter function, and that value is sitting at the first index of the array(it is not literally sitting on an index!). The algorithm will then just take a time of O(1) to complete. Why? Because the function was able locate it almost immediately without having to traverse the entire array. This is why the time taken to push a value into an array is always O(1). The array simply creates a new index at the end and pushes the new value into that index. However, the time taken to shift/unshift a value is O(n). Why? Every time you shift/unshift a value, the array will have to change the indices of all the values inside it and the time taken to do this depends on the length of the array. Hence the time taken to shift/unshift is O(n). O(1) is the best output you can get out of an algorithm. It is even better than O(logn).

O(nlogn):

This notation is actually better that O(n²),but worse than O(n). It doesn’t sound all great, right? But it is one of the best outputs you can get from a sorting algorithm. Sorting, regardless of what you do, takes time. When your program is sorting an array, it swaps the elements of the array, until they are completely sorted. That’s going to cost a lot of time no matter what.  With that said, I will have to briefly discuss  the merge sort algorithm to understand this notation. The time complexity of the merge sort algorithm is O(nlogn). However its space complexity is O(n). I’ll explain why. So the merge sort algorithm goes like this.

Confusing? I totally agree. However we are not trying to understand the merge sort algorithm. We are just trying to understand the notation, O(nlogn). With that said, we have two parts to consider here; ‘n’ and ‘logn’. Firstly ,according to the algorithm, the code splits the array into many halves, and stops when it can’t go any further. This splitting-up process equals to O(logn). Now we have our first part. Secondly, according to the algorithm, the code merges and sorts the splitted-up arrays. It sorts them by comparing the values of the splitted-up arrays. This process of merging and sorting equals to O(n), because the comparisons made here depends on the number of values the array has. When we multiply these two, we get O(nlogn). I know that this makes very little sense to you now. If you can properly understand the merge sort algorithm, you will get a hang of this. The space complexity of the merge sort algorithm is O(n), as you have to store the splitted-up arrays; and that depends on the length of your array.

We‘ll see more things about Big O in my forthcoming articles. There are minor methods you can use to accurately determine the Big O of your code. I hope you found this article useful and welcome to the world of algorithms! Stay tuned! I’ll be back.

Further reading