Geek asks and answers

Difficulty (initial question)

What is the complexity of these statements?

for(int k = 1; k < n; k++)
    for(int i = 0; i < n-k; i++){
        //O(1) operation here
    }

Explanation appreciated.

+3
source share
1 answer

First, go into the outer loop, you perform the operation n-1once. Secondly, you do it n-2once ... Add them all and you are done with the operations (n)*(n-1)/2.

To see this amount, write it from 1 to (n-1), then from (n-1) to 1 and add each member one by one.

  1   2   3 ... n-3 n-2 n-1
n-1 n-2 n-3 ...   3   2   1
---------------------------
  n   n   n       n   n   n

So 2 * sum = (n-1) * n.

So, roughly n²in terms of complexity.

+4
source

More articles:


All Articles