Big-O Notation

Section 1: What is it?

Big-O Notation helps us talk about the time taken by an algorithm to run given a particular input size.

Section 2: Why do we need it?

Imagine there are multiple solutions to a single problem but with different approaches/data structure, how do you know which one is better? Do you choose the solution that was the easiest to code or the solution you wrote and not the one your colleague did. Do we run both of them and decided by what is finished quicker? But what if one of the solutions is in a low-level/faster language than the other??

Big-O can help us identify which solution is better and provides a means of comparison that is independent of the programming language being used.It provides us a way to rate our implementations in a certain category to compare the efficiency of the approach.A scale to judge our algorithm if you think about it.

Section 3: Counting operations

Depending on how many assignment, mathematical, and comparison operation are done in a given program we can count the number of operations and have a rough estimate of how much computation is done by the program.

Take for example the given sample snippet below below:

1
2
3
4

int sum = 0; // 1 assignment operation
for (int i = 0 ; i < n ; i++ ) { // 3 * n operations
    sum = sum + i; // 2 operations
}

By a rough estimate the program above will do around (3n+3) operations.

But the cool kids don’t say our algorithm has (3n+3) operations, they say my algorithm has a Big-O of O(n). Which means my program for an input size of n does on a general scale around n operations.

Section 4: Some Handy Tricks while calculating Big-O Notations

• Constants don’t matter : 5n becomes n, 10000n^2 becomes n^2, (3n+3) will become n
• Constant Runtime : If an algorithm does a constant number of operations regardless of the input size the algorithm is a constant time algorithm and has a Big-O of O(1).
• We only take the largest terms into consideration: In an expression like (n^2+n) we only take n^2 into consideration.
• Most arithmetic,assignment and comparison operations are constant: Adding 2+2 takes roughly the same time adding 1000000+10000000, similarly assignment and comparison operation take the same time regardless of the size of the number.
• Accessing elements using an index,key is constant: When accessing elements in an array using an index, or a map/object using a key the operation is considered constant time.
• Inside a loop the complexity is the amount of times the loop will run muliplied by the total number of operations inside the loop.

Section 5: Sample Problem

The two functions given below calculate the Maximum Pairwise produt from a given list, i.e take any two numbers from an array/list such that their product is the largest compared to all the other pairs.

For a sampple array 1,4,5,6,3,5,4,6

The maximum pairwise product would be 6*5 that is 30

Lets take two solutions that solves the above problem and we will calculate which is more efficient using Big-O.

Solution 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public static int maxPairWiseMultiplicationNaive(int[] inputData){

    int maxProduct = -1;

    for (int i = 0; i < inputData.length ; i++ ){
        for( int j = 0; j < inputData.length ; j++){

            if ((inputData[i] * inputData [j]) > maxProduct )
                maxProduct = inputData[i] * inputData[j];
        }
    }

    return maxProduct;
}

By taking into consideration the rules from section 4. Inside the first loop, there is a nested loop so the complexity of this solution would be O(n^2) we ignore all constants and take into account only the highest term.

Solution 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public static int maxPairWiseMultiplicationEff(int[] inputData){

    int maxProduct = -1;
    int largestNumberIndex = -1;
    int secondLargestNumberIndex = -1;


    for (int i = 0 ; i < inputData.length ; i++ ){
        if ( largestNumberIndex == -1 || (inputData[i] > inputData[largestNumberIndex])){
            largestNumberIndex = i;
        }
    }


    for (int i = 0; i < inputData.length ; i++ ){
        if ((secondLargestNumberIndex != largestNumberIndex) &&
            ( secondLargestNumberIndex == -1 ||
            inputData[i] > inputData[secondLargestNumberIndex] ) ){

            secondLargestNumberIndex = i;
        }
    }

    return inputData[largestNumberIndex] * inputData[secondLargestNumberIndex];

}

The second approach on the other had uses two loops instead of a nested loop, So the complexity would come oy to be rough (n + n) => 2n => n , ie O(n) because we ignore the constants.

Section 6: Conclusion

An algorithmic approach with a complexity of O(n) is a far better approach than an algorithm with a time complexity of O(n^2),