Time Complexity. How is the time complexity of code O(n)^3

#1

bool find3Numbers(int A[], int arr_size, int sum)
{
int l, r;

/* Sort the elements */
sort(A, A + arr_size); 

/* Now fix the first element one by one and find the 
   other two elements */
for (int i = 0; i < arr_size - 2; i++) { 

    // To find the other two elements, start two index 
    // variables from two corners of the array and move 
    // them toward each other 
    l = i + 1; // index of the first element in the 
    // remaining elements 

    r = arr_size - 1; // index of the last element 
    while (l < r) { 
        if (A[i] + A[l] + A[r] == sum) { 
            printf("Triplet is %d, %d, %d", A[i], 
                   A[l], A[r]); 
            return true; 
        } 
        else if (A[i] + A[l] + A[r] < sum) 
            l++; 
        else // A[i] + A[l] + A[r] > sum 
            r--; 
    } 
} 

// If we reach here, then no triplet was found 
return false;

}

#2

Hi Stuti, first of all the time complexity of this operation is O(N^2) and not O(N^3). Let’s see how:
We have 2 loops:

for ( … ) {
while ( … ) {
…
}
}

Now for loop will get executed N times. And the inner loop will take values as:

At i = arr_size-3, while runs 1 time
At i = arr_size-4, while runs 2 times
…
…
At i = 0, while runs arr_size times

So total no. of steps that are getting executed are`:

1 + 2 + 3 + 4 + … + N-1 + N
= N(N+1) / 2
Now Time Complexity becoms O( N(N+1)/2) = O(N^2). This is because we neglect constant terms.

Hope this helps :slight_smile:

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.