unnieyah -4 years ago 154

Java Question

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

}

}

}

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**

Latest added