Time Complexity Analysis : better explaination?

Question

I came across the following code to find triplets that satisfy Triangle sum property.

// Function to count all possible triangles with arr[]
    // elements
    static int findNumberOfTriangles(int arr[])
    {
        int n = arr.length;
        // Sort the array elements in non-decreasing order
        Arrays.sort(arr);

        // Initialize count of triangles
        int count = 0;

        // Fix the first element.  We need to run till n-3 as
        // the other two elements are selected from arr[i+1...n-1]
        for (int i = 0; i < n-2; ++i)
        {
            // Initialize index of the rightmost third element
            int k = i + 2;

            // Fix the second element
            for (int j = i+1; j < n; ++j)
            {
                /* Find the rightmost element which is smaller
                   than the sum of two fixed elements
                   The important thing to note here is, we use
                   the previous value of k. If value of arr[i] +
                   arr[j-1] was greater than arr[k], then arr[i] +
                   arr[j] must be greater than k, because the
                   array is sorted. */
                while (k < n && arr[i] + arr[j] > arr[k])
                    ++k;

               /* Total number of possible triangles that can be
                  formed with the two fixed elements is k - j - 1.
                  The two fixed elements are arr[i] and arr[j].  All
                  elements between arr[j+1] to arr[k-1] can form a
                  triangle with arr[i] and arr[j]. One is subtracted
                  from k because k is incremented one extra in above
                  while loop. k will always be greater than j. If j
                  becomes equal to k, then above loop will increment
                  k, because arr[k] + arr[i] is always/ greater than
                  arr[k] */
                count += k - j - 1;
            }
        }
        return count;
    }

Can someone give a better explanation as to why the time complexity of this solution is O(n^2) and not O(n^3) ? My understanding is that for every i and j, k varies too.

Answer 1

The time complexity of the above solution is O(n^2) as you can see the value of k is initialised before the second for loop. In the second for loop the value of k is increasing in while condition. Once the while condition terminates, for loop will run for the next value of j and the value of k remains the same as it was terminated in the while loop before. Once the value of k becomes equal to n then it will not run for any value of j after that.

So the second for loop is running only from k=i+2 to n. Hence the complexity is O(n^2).

Answer 2

The only statement that could get executed more than O(n^2) times is the most nested ++k statement.

But k never exceeds n, and is reset (to a non-negative number) n-2 times. That proves that the ++k statement is executed at most n(n-2) = O(n^2) times.