Time complexity of the algorithm?

Question

This is the algorithm: I think its time complexity is O(n^2) because of loop in loop. How can I explain that?

FindSum(array, n, t) 
i := 0 
found := 0 
array := quick_sort(array, 0, n - 1) 
 while i < n – 2 
            j = i + 1 
            k = n - 1 
        while k > j 
             sum = array[i] + array[j] + array[k] 
             if sum == t 
                 found += 1 
                  k -= 1 
                  j += 1 
            else if sum > t 
                 k -= 1 
            else 
                 j += 1 

Answer 1

Yes, the complexity is indeed O(n^2).

The inner loops runs anywhere between k-j = n-1-(i+1) = n-i-2 to (k-j)/2 = (n-i-2)/2 iterations.

Summing it up for all possible values of i from 0 to n-2 gives you:

T = n-0-2 + n-1-2 + n-2-2 + ... + n-(n-2)-2
  = n-2 + n-3 + ... + 0

This is sum of arithmetic progression, that sums in (n-1)(n-2)/2 (sum of arithmetic progression), which is quadric. Note that dividing by extra 2 (for "best" case of inner loop) does not change time complexity in terms of big O notation.