Giovanni Berti Giovanni Berti - 1 year ago 64
Java Question

Difference of complexity between double nested for loops? (Java)

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

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