Big O

intro

O(n) #

Let’s say we have an array of one element, and we are looping through that array in order to find an element. This will be pretty fast. But if we put 100 elements in that array, looping through it will be a bit slower. With 10000 element, even slower. This means that our code is a Big 0 notation of O(n) (linear time to find the record while the number of operations increase).

O(1) #

    def getNumber(numbersArray):
        for i in numbersArray:
            print(i)

    getNumber(myArray[0])

If we always pass to the above function only the first element of an array, no matter how big it is, we will always have constant time. O(1) is very scalable and predictable and that’s why it is in green colour in the graph above.

Calculate Big O #

To calculate Big O Complexity, we can use the following 4 rules

Rule 1: Worst Case #

Assume that we a loop that looks for a particular value in an array. When we find the value, we can break out of the loop, saving operational time. Best case is to have the record in the first positions, but the worst case scenario is that it is last. So that makes the complexity O(n).

Rule 2: Remove Constants #

Having this pseudo code

print(itemsArray[3]) //O(1)
halfArray = itemsArray.length / 2  
index = 0;  //O(1)
while (index < halfArray) {   // O(n/2)
   print(itemsArray[index]
   index++
}

for (i = 0; i < 100; i++) {   //O(100)
   print(i)
}

The result is O(1 + n/2 + 100). This eventually will become a O(n), because when n is getting larger and larger, it doesn’t matter if we add 1 or 100 more constants to the end result and same goes to the divide by 2.

Rule 3: Different Terms for Inputs #

Having this pseudo code

myFunction(inputArray1, inputArray2) {
     for (i = 0; i < inputArray1.length; i++) {
        print(i)
     }
     for (i = 0; i < inputArray2.length; i++) {
        print(i)
     }
}

The complexity of the above code, since the function has 2 different inputs, cannot be O(n), since one array can have 1000 elements and the second one 1000000. Here, the complexity is O(n+m).

Drop non Dominants #

myFunction(inputArray) {
     for (i = 0; i < inputArray.length; i++) {
        print(i)
     }
     for (i = 0; i < inputArray.length; i++) {
        for (y = 0; i < inputArray.length; y++) {
            print(i+y)
        }
     }
}

We would say that the complexity here is O(n + n^2). But when applying this rule, as the n grows, n^2 becomes way more important than n, so we remove it, and the complexity becomes O(n^2).

O(n^2) #

Having the following code block:

arr = [1, 2, 3, 4]

def pairs(array):
    for i in array:
        for y in array:
            print("pair: ", i, "-", y)

The general rule of thumb, is that when we have nested loops, the complexity is O(n*n) = O(n^2), which is called Quadratic Time.

/*54745756836*/