What is the time complexity of this doubly-nested loop?

Question

Hi i am a bit confused about time complexity of following snippet, It would be great if some one can shed light on this.

     for ( i = 1; i <= n ; i ++)
        for ( j= i+1; j <= n; j++)
          //print something

Answer 1

In cases like these, keep this in mind:

When in doubt, work inside out!

Let's take your code:

 for ( i = 1; i <= n ; i ++)
    for ( j= i+1; j <= n; j++)
      //print something

Here, the cost of printing something is Θ(1) (assuming you're always printing the same thing), so we can rewrite this code like this:

 for ( i = 1; i <= n ; i ++)
    for ( j= i+1; j <= n; j++)
       do Θ(1) work

Now, let's work from the inside out. What is that inner loop going to do? Well, when i = 1, it's going to run for n - 1 iterations. When i = 2, it's going to run for n - 2 iterations. When i = 3, it's going to run for n - 3 iterations. In that sense, the work done is Θ(n - i), so we can replace the inner loop with something like this:

 for ( i = 1; i <= n ; i ++)
    do Θ(n - i) work

Now, let's look at this outer loop. The first time through, this is going to do (roughly) n - 1 work, the second time it'll do n - 2 work, the third time it'll do n - 3 work, etc. In other words, the total work done here is (roughly) equal to

(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1

This is a famous sum called Gauss's sum, and its value is n(n - 1) / 2, which is Θ(n²). Consequently, the total work done here is Θ(n²), as @Lashane pointed out in their comment.