-1
int Solution::diffPossible(vector<int> &A, int B) {
    for (int i = 0; i < A.size(); i++) {
       for (int j = i+1; j < A.size(); j++)
          if ((A[j]-A[i]) == B)
             return 1;      
    }
    return 0;
}

This is the solution to a simple question where we are supposed to write a code with time complexity less than or equal to O(n). I think the time complexity of this code is O(n^2) but still it got accepted. So, I am in doubt please tell me the right answer.

0

1 Answer 1

3

Let's analyze the worst-case scenario, i.e. when the condition of the if-statement in the inner loop, (A[j]-A[i]) == B, is never fulfilled, and therefore the statement return 1 is never executed.

If we denote A.size() as n, the comparison in the inner loop is performed n-1 times for the first iteration of the outer loop, then n-2 times for the second iteration, and so on...

So, the number of the comparisons performed in the inner loop for this worst-case scenario is (by calculating the sum of the resulting arithmetic progression below):

n-1 + n-2 + ... + 1 = (n-1)n/2 = (n^2 - n)/2
^                 ^
|_________________|
     n-1 terms

Therefore, the running-time complexity is quadratic, i.e., O(n^2), and not O(n).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.