Reputation: 254
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
}
}
Upvotes: 3
Views: 4676
Reputation: 186833
Both loops have the same assimptotic behaviour - O(n**2)
1 + 2 + ... + n = n(n+1)/2 = n*n/2 + n/2 -> O(n**2)
n*n -> O(n**2)
So 2nd loop is near as twice as slow than the 1st loop, while the assimptotic is the same
Upvotes: 3
Reputation: 727077
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:
#
##
###
####
#####
######
Upvotes: 8