unnieyah unnieyah -4 years ago 154
Java Question

How to find the asymptotic complexity of 3Sum.java

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++;
}
}
}
}

Answer Source

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).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download