Giovanni Berti - 1 year ago 71

Java Question

What's the difference in terms of performance and complexity between these two nested for loops?

`for(int i = 0; i < l.length; i++) {`

for(int j = 0; j <= i; j++) {

//do something

}

}

and :

`for(int i = 0; i < l.length; i++) {`

for(int j = 0; j < l.length; j++) {

//do something

}

}

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

Answer Source

The first loop is about twice as fast as the second one, but in terms of the asymptotic time complexity they are the same:

```
O(N^2)
```

You can think anout it graphically: imagine a square with N units on each side. The second loop visits all unit squares;

```
######
######
######
######
######
######
```

the first loop visits the points that belong to a triangle covering half the square:

```
#
##
###
####
#####
######
```

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