CODEWITHSUNDEEP
algorithm
Abdul Hameed M
Abdul Hameed M

Reputation: 21

Frequency of less than compare algorithm

Frequency of less than compare for below code is (N+1)(N+2)/2.

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

I think N+1 is for first loop. What about (N+2)/2, any idea?

Upvotes: 0

Views: 75

Answers (1)

tobias_k
tobias_k

Reputation: 82929

In the first iteration, the inner loop runs N-1 times, in the second iteration N-2 times, and so on. Each time, the < operation is checked once more (when the condition no longer holds), thus N + N-1 + N-2 + ... + 1 checks of < in all iterations of the inner loop. In the outer loop, < is checked an additional N+1 times, for a total of N+1 + N + ... + 1 times. That sum is equal to (N+2)*(N+1)//2.

You can also visualize the number of iterations as a (jagged) triangle:

#####
####
###
##
#

Normally, a right-angled triangle with side lengths N+1 would have an area of (N+1)*(N+1)//2, but since its hypothenuse is "jagged", its an additional (N+1)//2 (being N+1 smaller triangles with side-length 1), which again adds up to (N+2)*(N+1)//2

Upvotes: 1

Related Questions