CODEWITHSUNDEEP
time-complexity
Muhib Al Hasan
Muhib Al Hasan

Reputation: 302

How can I calculate the complexity of this code snippet?

I can't calculate the Time Complexity of this code.

for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
        //statement
    }
}

Need help.

Upvotes: 1

Views: 1579

Answers (3)

Raj Datta Manohar
Raj Datta Manohar

Reputation: 167

For every ith element the second loop runs n-(i+1) times. In the first for loop when i=0, the second loop runs n-1 times
Similarly when i=1 second loop runs n-2 times
.
.
.
when i=n-2 second loop runs 1 time.
when i=n-1 second loop runs 0 times.
O(n-1)+O(n-2)+......+O(1)+0 => O(n)
Hence the total algorithm's time compexity is O(n*n) = O(n^2)

Upvotes: 0

Paul92
Paul92

Reputation: 9062

Let's try counting the operations. The problem is which operations are relevant? The time complexity is usually expressed in big-Oh notation (or other asymptotic notations), because it hides the difficulty of counting operations exactly. Therefore, anything which is a constant can be counted as 1. It's irrelevant if there are 4 additions or 40, what is relevant is how many times this repeats. In the end, how many times statement is executed.

Let's count then. The outer loop goes from 0 to n, while the inner loop goes from i+1 to n. So, when i is 0, the inner loop does n-1 iterations, when i is 1, the inner loop does n-2 iterations, and so on, until i is n-1 and the inner loop doesn't execute anymore. So, we have:

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

In total, there are n terms there. This sum of consecutive numbers has a quite well known formula: it is (n-1)(n-2)/2.

Expanding the product above, we get 1/2(n^2-3n+2). And O(1/2(n^2-3n+2)) is equivalent to O(n^2).

As to why everything reduces to O(n^2), there is a lot behind the theory of asymptotic notation, but, in practice, it reduces to "big-oh keeps the most significant term in a polynomial and discards coefficients" (easily proven with the definition of big-Oh).

Upvotes: 3

Yunhai
Yunhai

Reputation: 1411

O(n^2)

Iteration start from n when i=0 then n-1, n-2 until hitting the last iteration, which is 0;

So the total iteration will be n + (n-1) + (n - 2) + 。。。+ 0 = O(N^2)

Upvotes: -1

Related Questions