Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have a method that finds 3 numbers in an array that add up to a desired number.

public static void threeSum(int[] arr, int sum) {
    quicksort(arr, 0, arr.length - 1);
    for (int i = 0; i < arr.length - 2; i++) {
        for (int j = 1; j < arr.length - 1; j++) {
            for (int k = arr.length - 1; k > j; k--) {
                if ((arr[i] + arr[j] + arr[k]) == sum) {
                    System.out.println(Integer.toString(i) + "+" + Integer.toString(j) + "+" + Integer.toString(k) + "="  + sum);
                }
            }
        }
    }
}

I'm not sure about the big O of this method. I have a hard time wrapping my head around this right now. My guess is O(n2) or O(n2logn). But these are complete guesses. I can't prove this. Could someone help me wrap my head around this?

share|improve this question

3 Answers 3

up vote 7 down vote accepted

The running time is O(n3). You have three nested loops:

  • Approximately n iterations of i
  • For each i, approximately n iterations of j
  • For each (i, j) pair, up to about n iterations of k. On average, it take just 0.5 * n iterations of k, but the constant factor doesn't matter.

Quicksort is generally O(n log n). So the total is O(n log n + 0.5 n × n × n), which is O(n3).

Since you took the trouble to sort the array, the innermost loop could be replaced by a binary search, which is O(log n). Therefore, an improved algorithm could work in O(n2 log n).

share|improve this answer
    
Oh wow Binary search within the inner loop! Never though of that thank you! –  Liondancer Apr 3 at 7:33

This won't change the Big O but the second loop can start at j = i + 1.

share|improve this answer

Are you looking for three distinct numbers, or can i, j, and k be the same? The loop limits suggest that you expect the numbers to be distinct. However, you don't actually check that the results are distinct.

To be consistent, you should either:

  • Make all three loops consider entries from the entire array, or
  • Discard solutions where i = j or where j = k or where i = k.
share|improve this answer
    
I figured out the big O of my program. However you made a really good point about the values of the numbers. I am going to look into this! –  Liondancer Apr 3 at 7:25
    
O(n^3) for those wondering –  Liondancer Apr 3 at 7:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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