Big O in Programming

Program execution takes time and memory and it depends on processing speed of the computer on which program is being executed. It may take 1sec to execute a piece of code on my machine while same code can take more or less time on another machine depending on its processing power. So it means that we can’t measure code performance on basis of execution time and it should be independent of machine resources.

A good code has two qualities:

• Readability
• Scalability

Readability means that code is readable and easy to understand for developers. It generally means that code should have proper coding styles, formats, naming conventions and commenting such that other developers find it easy to work with your code.

Scalability means that code should be easily scalable for larger inputs and shouldn’t break. For instance, if an app currently has thousand users and in future, the userbase grows to millions, the app should work the same. To develop scalable apps, Big O analysis of code is performed and code is made as efficient as possible.

Big O notation is used to evaluate performance matrix of code in term of Space and Time Complexity. It tells how well the code will perform for larger inputs by estimating execution time and space irrespective of the hardware it is being executed on.

Time Complexity: Estimated amount of Time required for execution

Following points will help you how to calculate Big O Time Complexity of a code:

• Big O of =, +, -, *, /, % is 0(1)
• Big O of loop is O(N) where N is the number of times the loop executed
• Big O is always estimated for worst case scenario
• Generally, O(1) + O(1) + … = O(1) and O(N) + O(N) +…= O(N)
• Also, we neglect constant terms and assignments and only calculate Big O of loops and expensive operations.
• Big O of nested loop is O(N) * O(N) = O(N²)
• For different inputs of nested loops, O(N) * O(M) = O(N*M) = O(P)

Consider this code:

def TwoSum(numbers, target):
    mapValues = {}                                     O(1)
    for i in range(len(numbers)):                      O(N):N=length
        currentVal = mapValues.get(numbers[i], None)   O(1)
        if(currentVal is not None):                    O(1)
            return [currentVal, i]                     O(1)
        else:
            numberToFind = target - numbers[i]         O(1)
            mapValues[numberToFind] = i                0(1)
    return None                                        O(1)

Note: Statements inside loop will execute N=length of numbers times, so their complexity will be multiplied with O(N)
Big O = O(1) + O(N)*(O(1) + O(1) + O(1) + O(1) + O(1)) + O(1)
As O(1) + O(1) +O(1) + ... = O(1), so
      = O(1) + O(N)*(O(1) + O(1)
Also O(1) + O(N) = O(N) and O(1)*O(N) = O(N)
      = O(1) + O(N) + O(1)
      = O(N) 

O(N) is a general term where N stands for large number. We can estimate N/2, N/3 to be equal to N when N is too large.

Now we can see that ultimately, the complexity depends on how many times the loop is executed and it is generally not calculated for small operations like calculations and assignments.

Space Complexity: Estimated amount of memory required by program

Space Complexity is calculated in term of variable initialization inside the program. Space complexity depends on:

• Variables
• Data structures
• Functions calls
• Allocations

Consider the example below for better understanding:

newArray = []                O(1)
for i in range(n):
    newArray.append(i);      O(N)
Big O = O(1) + O(N) = O(N)

Here the space complexity is O(N) because new memory is allocated for array N times.

For Big O calculation, it is generally estimated that the number of inputs are very large and hence small operations can be neglected, only repetitive operations are considered.