Difference of complexity between double nested for loops? (Java)
for-loop, java, performance, time
Solution
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:
#
##
###
####
#####
######
Problem
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 } } ```