 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++;
}
}
}
}
`````` jack jay

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