Back to basics - The Big O (Part 1)
Tags: bigo, algorithms, datastructures, coding
Published: 2021-01-31 18:24:13

An algorithm has always been used as a synonym when we, as Software engineers, don't want to explain what we are doing (or often don't even know what we are doing). So what is an algorithm?

    An algorithm is the sum of steps that we take to achieve something.

That something could be a problem we are trying to solve or just some tasks that we usually do. For example, waking up in the morning and preparing our coffee, and then sitting behind our laptops. These steps could be considered an algorithm. The steps we take in this example are:

    1 - Waking up
    2 - Making some coffee
    3 - Sitting behind our laptops

In software, we are doing no different. But the software doesn't wake up or make coffee. The computer analyzes data, and by analyzing, I mean reading, deleting, inserting, etc., and the data could be as simple as just the arrays.

The next step is to make these algorithm steps as efficient as possible. In the end, it's always better to walk a few steps than a few miles.

![o-log-n-blue](https://dev-to-uploads.s3.amazonaws.com/i/aorhcqcucof867ujn4cq.jpg)

**An algorithm is the steps taken to solve a particular problem**, and with the help of the Big O, we can measure these steps.

--------------------

When we see a sample code, we have to ask ourselves whether this piece of code has been written as efficiently as possible.

As a more experienced programmer, you should not be satisfied when your algorithm just 'works.' It should work in the most efficient way possible.  
 
 --------------------

The key question that Big O is trying to answer is: If there are N data elements, how many steps will the algorithm take to finish its work **and how will these steps change if the data increases.** In other words, we can measure an algorithm's efficiency with the Big O notation.

There are multiple ways to use Big O to measure an algorithm: 

     1- The best way "O of one" --> O(1): 

Measuring a particular algorithm by taking the same number of steps despite how big the data (an array, for example) is.

Example: Reading a value from an array will take "always" one step to finish. 

     2- A less efficient way "O of N" --> O(N): 

Measuring a particular algorithm by taking the N number of the data (an array, for example). If the array is 10, it may take 10 steps, and if the array is 1000, it may take 1000 steps.

Example: searching an array with a for-loop. It will loop throw all the array values till it finds the searching one. 

    3- An even less efficient way "O of N2" --> O(N2):

This will happen when we make a nested loop. So we will start by searching one value from the first loop and loop throw the whole second loop to find this value, and then we do the same with the rest of the first loop. 

    4- The good way "O of log N" --> O(log N):

This needs a little bit more explanation: 

Log means Logarithm, and a logarithm means the inverse of exponents: 

* --> 2 to the power 3 = 8
* --> log2 8  = 3
* --> log2 64 = 6
* --> How many times do we need to divide 64 by 2 until we end up with 1? 6 times 

So, O(log N) means measuring an algorithm that increases one step each time the data is doubled.

In other words: an algorithm takes as many steps as it takes to keep halving the data elements until we remain with one element.

For example, the binary search. I will explain it in the next part of this back to basics series.