0

I have the below code to return the index of 2 numbers that add up to the given target. What is the time complexity of the code? Explanations are appreciated. Thanks.

int[] result = new int[2];
    int i=0, k=i+1;
    while (i < nums.length)
    {
        if(nums[i]+nums[k]==target && i!=k)
        {
            result[0]=i;
            result[1]=k;
            break;
        }    
        else if (k < nums.length-1)  
            k++;
        else
        {
            i++;
            k=i;
        }
    }
   return result;
Abhishek Bhagate
  • 5,583
  • 3
  • 15
  • 32
parul jain
  • 29
  • 3
  • this might help -https://stackoverflow.com/a/9958802/13660279 – bp41 Jun 19 '20 at 20:42
  • Downvoted because no attempt whatsoever. You are expected to try it yourself first and then explain what exactly is unclear to you. – Zabuzard Jun 19 '20 at 20:45

2 Answers2

1

Time Complexity

The worst-case time complexity of the given code would be O(N^2) , where N is nums.length.

This is because you are checking each distinct pair in the array until you find two numbers that add upto the target. In the worst case, you will end up checking all the pairs. The number of pairs in an array of length N would be N^2. Your algorithm will check for N*(N-1) pairs which comes out to be N^2 - N. The upper bound for this would be O(N^2) only since lower order terms are neglected.

Flow of Code

In the code sample, here's how the flow occurs -

  • i will start from 0 and k will be i+1 which is 1. So, suppose that you won't find the pair which add up to the target.

  • In that case, each time ( from i = 0 to i = nums.length-1), only the else if (k < nums.length-1) statement will run.

  • Once k reaches nums.length, i will be incremented and k will again start from i+1.

This will continue till i becomes nums.length - 1. In this iteration the last pair will be checked and then only the loop will end. So worst-case time complexity will come out to be O(N^2) .

Time Complexity Analysis -

So you are checking N pairs in the first loop, N-1 pairs in the next one, N-2 in next and so on... So, total number of checked pairs will be -

N + ( N-1 ) + ( N-2 ) + ( N-3 ) + ... + 2 + 1
= N * ( N + 1 ) / 2
= ( N^2 + N ) / 2

  • And the above would be considered to have an upper bound of O(N^2) which is your Big-O Worst-Case time complexity.

  • The Average Case Time Complexity would also be considered as O(N^2).

  • The Best Case Time Complexity would come out to be O(1) , where only the first pair would be needed to be checked.

Hope this helps !

Community
  • 1
  • 1
Abhishek Bhagate
  • 5,583
  • 3
  • 15
  • 32
  • 1
    @Zabuzard The time complexity is still `O(N^2)`. The numbers of checked pairs will be `N*(N-1)`. I have made the edit to mention the same. – Abhishek Bhagate Jun 19 '20 at 20:52
1

Premise

It is hard to analyze this without any additional input how nums and target correspond to each other.

Since you do not provide any additional information here, I have to assume that all inputs are possible. In which case the worst case is that none of the pairs buildable by nums can form target at all.

A simple example explaining what I am referring to would be target = 2 with nums = [4, 5, 10, 3, 9]. You can not build target by adding up pairs of nums.

Iterations

So you would end up never hitting your break statement, going through the full execution of the algorithm.

That is, the full range of k from 0 to nums.length - 1, then one increment of i and then k again the full range, starting from i. And so on until i reaches the end as well.

In total, you will thus have the following amount of iterations (where n denotes nums.length):

n, n - 1, n - 2, n - 3, ..., 2, 1

Summed up, those are exactly

(n^2 + n) / 2

iterations.

Complexity

Since all you do inside the iterations is in constant time O(1), the Big-O complexity of your algorithm is given by

(n^2 + n) / 2 <= n^2 + n <= n^2 + n^2 <= 2n^2

Which by definition is in O(n^2).

Alternative code

Your code is very hard to read and a rather unusual way to express what you are doing here (namely forming all pairs, leaving out duplicates). I would suggest rewriting your code like that:

for (int i = 0; i < nums.length; i++) {
    for (int j = i; j < nums.length; j++) {
        int first = nums[i];
        int second = nums[j];

        if (first + second == target) {
            return {i, j};
        }
    }
}

return null;

Also, do yourself a favor and do not return result filled with 0 in case you did not find any hit. Either return null as shown or use Optional, for example:

return Optional.of(...);
...
return Optional.empty();
Zabuzard
  • 25,064
  • 8
  • 58
  • 82