CODEWITHSUNDEEP
javaperformancefor-looptime
Giovanni Berti
Giovanni Berti

Reputation: 254

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

Upvotes: 3

Views: 4676

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186833

Both loops have the same assimptotic behaviour - O(n**2)

  1. 1st loop: 1 + 2 + ... + n = n(n+1)/2 = n*n/2 + n/2 -> O(n**2)
  2. 2nd loop: 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

Sergey Kalinichenko
Sergey Kalinichenko

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

Related Questions