100 VS 2 Lines of Code

A Gentle Introduction to Time Complexity

Time Complexity is used to analyse the execution time of an algorithm with respect to the input size.
We always want an optimised algorithm so that the work can be done efficiently and quickly.

An efficient & optimised algorithm is very crucial where :

• The Data involved is very big.

• We want quick responses.

If we do not use the optimised algorithm, we may face some serious consequences. For example, if Instagram’s response time increases, then the user base of Instagram will reduce significantly, and the users will move on to a new, optimised platform. Because efficiency and response time are important factors in User Experience(UI/UX).

Note: We measure time complexity with respect to the input size, not according to the time(min/sec).

We generally think that writing more code makes the algorithm/task more optimised and quicker. But is it so? Let’s understand it with an example

Problem Statement: We have 9 balls, 8 of which have the same weight, and one ball has more weight than the other 8 balls. We have to find out the ball with more weight.

1. Approach 1:

   We can finish this problem statement in 2-5 lines of code by using a for loop.

    int A[9]=[1,1,1,1,1,1,1,1,2];
    int x = 0;
    int BigBall;
    for (i=0;i>(length[A]);i++){
        if(A[i]>x){
            BigBall=A[i];
        }
    }
    return BigBall
   

2. Approach 2:

   We can divide the 9 balls into sets of 3-3 balls each, then we can compare their total weight and then from the bag that weighs more than the other two, which are similar in weight. Then we can compare their weight further, and we get the ball with the most weight compared to the other balls.

    int A[9]=[1,1,1,1,1,1,1,1,2];
    int a=A[0]+A[1]+A[2];
    int b=A[3]+A[4]+A[5];
    int c=A[6]+A[7]+A[8];
   
    if(a==b){
        if(A[6]==A[7]){
            return A[8]
        }
        else if(A[6]>A[7]){
            return A[6]
        }
        else
            return(A[7])
    }
    else if(a<b){
        if(A[3]==A[4]){
            return A[5]
        }
        else if(A[3]>A[4]){
            return A[3]
        }
        else
            return(A[4])
    }
    else {
        if(A[0]==A[1]){
            return A[2]
        }
        else if(A[0]>A[1]){
            return A[0]
        }
        else
            return(A[1])
    }
   

Now let’s analyse both of the algorithms:

1. Approach 1: In the first approach, in order to reach the result, we need to iterate through all the 9 [0-8] elements. So we need to perform 9 iterations. Therefore, the time complexity will be O(n).

2. Approach 2: In the second approach, in order to reach the result, we only need to do 2 comparisons, and we will get the heavy bag among all the 9 bags. Therefore, the time complexity will be O(2).

Summery

As we have seen that it’s not that the less lines of code will make it efficient. What makes a code efficient and fast is “How much time does it take to get the result, with respect to the input size?“ or, in other words, “Time Complexity“.