Surviving Big O: Part I

Let's be honest- learning Big O is hard for beginners. This article is written so that you don't be afraid of such an innocent topic like Big O. As prerequisite I would recommend you to have some knowledge about loops and nested loops. Let's begin this survival mission-

Simply put, Big O is the sum of all the steps your algorithm takes from beginning to end. Now If you want to flex in front of someone then tell them this definition-

"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity" - Wikipedia

You don't even have to try to understand this. Even I don't know how this definition is related to Big O.

Now let's talk about importance of Big O. Suppose you have written an algorithm and it took 5 millisecond to run in your machine. So you told your friend- "see what a programmer I am. My algorithm runs in 5 milliseconds". Then your friend also ran the same algorithm in his machine and it took 1 millisecond to run. What the heck!!! Actually how many seconds our algorithm will take to run depends on a lot of things like CPU, processor, RAM, programming language etc. Then how are we going to know how fast or slow an algorithm is? This is where our Big O notation is the hero.
With the help of Big O, we can figure out how a code would perform if given a large input. Simply, how much steps the algorithm will take when its given a large input.

Let's see an example-
Suppose you wrote a program to get the sum of all numbers of an array.

def sum_of_array(numbers):
    sum = 0
    for num in numbers:
        sum += num

    return sum

First of all we have declared a variable named
sum. This is one step. So here the Big O is O(1) (The Syntax of Big O is A capital O and then inside parenthesis the number of steps). After the variable we are looping through the array. How are we going to count the Big O of this loop? We know that the loop will iterate through each and every element of the array and add the current number with the sum which is one step. If there are "n" elements in the array then the loop will add the current number "n" times. That means here the total steps will be- 1 * n = n. So we will add a "n" in our Big O- O(1 + n). After that we have a return statement. This return statement is 1 step. That means our final Big O is- O(1 + n + 1) = O(2 + n)

Now how are we going to know which one is one step and which one is "n" steps? When you're code won't depend on the input size that is one step and when it does that's "n" or "m" or "a" or "b" steps. (Note: you don't have to take "n". You can take any character. But taking "n" is a best practice). Let's understand steps with the above example. In the very first line we are declaring a variable sum and assigning 0 to it. It doesn't depend on the input size cause whatever the input size be we will assign 0 here. So it's one step. Next we have a for loop and this for loop depends on the input array size cause it's gonna run through all the elements of the input array till the end of the array. So if there are 5 elements it would run 5 times and if there are 100000 elements it would run 100000 times. So we are taking "n" steps here. At last we are return sum variable. Whatever the input size be we would return the sum variable so it doesn't depend on the input that's why its one step.

If you understand this far, then you are have learnt the fundamental of Big O.🤩🤩🤩

Now let's jump into another interesting example-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

Here we are drawing a square with the help of a nested for loop. I hope you all know how nested for loop works. What's the Big O's gonna look like here? The first for loop will run as many times as the input number is. Let's say the number is "n" Then the first for loop will run "n" times and the second for loop will run "n" times for each iteration of the first loop. That means it would run total n * n times. Recall in the first example we had multiplied 1 * n cause there were 1 step inside the for loop. As there are "n" steps inside the for loop here we are multiplying n * n = n^2. So the Big O here would be O(n^2). Next we have a print() statement inside the first for loop so it will run n * 1 = n. The final Big O will be- O(n + n^2).

If you understand all the above discussed things then learning Big O will be a piece of cake to you now.

Now I want to give you three fun little exercises. Try to solve them on your own first.

1st problem

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

Here for some reasons we are looping over the same array twice (Note: It's not a nested loop) and we are adding all the items to the sum variable in both loops.

2nd problem

def sum_of_two_array(arr1, arr2):
    sum1 = 0
    sum2 = 0
    for i in range(len(arr1)):
        sum1 += arr[i]

    for j in range(len(arr2)):
        sum2 += arr[j]

This one is almost the same as the previous one. But here you're given two input arrays. Remember we can't take "n" for both arrays. We have to take different characters for different inputs. Cause here the first input array can be of size 100000 and the second input array can be of size 5. Now try to solve the problem.

3rd problem

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

This problem also has two inputs just like the previous one. But this one is nested.

Solutions

1. O(2n)
   Because here we have two for loops one after another. If each for loop takes "n" steps then total steps will be- O(n + n) = O(2n)

2. O(n + m)
   Note: Here you can take any character. Taking "m" is not a must.
   Here we are iterating over two different arrays one after another that's why it's O(n + m)

3. O(n * m)
   Here we have a nested for loop but over two different arrays. That means for each iteration of first for loop we will iterate "m" times on the second for loop. (here "m" is the number of elements in the second array). So if the first for loop runs "n" times the total steps will be O(n * m)

You know the basics of Big O. Now we will talk about how to simplify big O. First I will state the rules-

1. Worst Case
2. Remove Constants
3. Different Terms for inputs
4. Drop non dominants

Rule 1: Worst Case
Whenever we are finding Big O of an algorithm we are always concerned about the worst case, that is how many steps the algorithm will take in the worst case. Example-

def search(numbers, target):
    for i in range(len(numbers)):
        if numbers[i] == target:
            return  i

In this code, we are searching for a given number. Now what will its big O look like? Suppose the target number is in the very first index of the array. Then we just need one step. That means O(1). But what if the target number is at the last index of the array? Then we will need to iterate through the whole array which is O(n). Then what will be the real big O? The real big O will be O(n) cause we are always concerned about the worst case when finding out the Big O. Cause if we can optimize the code for worst case it's gonna be optimized for other cases too.

Rule 2: Remove Constants

If there is any constant in the Big O you don't need to keep that. Let's understand it by the very first problem-

def sum(arr):
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

    for j in range(len(arr)):
        sum += arr[j]

we saw the big O here was O(2n) which is actually wrong. The real big O here is O(n) cause we need to remove the constants from the Big O.

Rule 3: Different Terms for inputs

We have learnt this rule in problem 2 and 3. Let's understand it again by problem 3:

def print_hash(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr2)):
            print("#")

Here two separate input arrays are given. So we need to take two different character or term for two different inputs. Here the Big O will be O(n * m)

Rule 4: Drop non dominants

We saw a example a long time ago-

 def print_square(number):
    for i in range(number):
        for j in range(number):
            print("*")
        print()

Here we said that the Big O is O(n + n^2) but "n" is smaller than "n^2" so we will drop "n" and the real big O here is O(n^2)

These were the four rules. Now you can find Big O for any algorithm. In the next part we will talk about some famous Big Os. See you there.