-1

how do you get the time complexity of the functions count and printall in ThreeSum.java?

public static void printAll(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                if (a[i] + a[j] + a[k] == 0) {
                    System.out.println(a[i] + " " + a[j] + " " + a[k]);
                }
            }
        }
    }
} 


public static int count(int[] a) {
    int n = a.length;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                if (a[i] + a[j] + a[k] == 0) {
                    count++;
                }
            }
        }
    }
jack jay
  • 2,493
  • 1
  • 14
  • 27
unnieyah
  • 3
  • 3

1 Answers1

0

Although time complexity questions are sometimes very tough but this one is an easy cake. You can simply check it out as follows,

for (int i = 0; i < n; i++) // it runs for n times
        for (int j = i+1; j < n; j++) // it runs for n-i-1 time
            for (int k = j+1; k < n; k++) // it runs for n-j-1 times

Now since they are nested loops that means each of inner loop runs as many number of times as outer loop.

total = n * ( n-i-1 ) * ( n-j-1 ) 
      = n^3 ... // ignoring all other lower power terms

So time complexity of this code will be O(n^3).

jack jay
  • 2,493
  • 1
  • 14
  • 27
  • If it helps you kindly accept the answer so that others can also take help from this. – jack jay Mar 01 '17 at 02:49
  • done. so the if statement doesn't affect the time complexity at all? – unnieyah Mar 01 '17 at 02:53
  • yes its contributing but very little when you compared it with `n^3`. For time complexity we generally take loops as major cause of time taking in program. – jack jay Mar 01 '17 at 03:01