Definition of time complexity

Question

Given the following pseudocode for array A

x = 0
  for i = 0 to n - 1
    for j = i to n - 1
       if A[i] > A[j]:
          x = x + 1
  return x

How to determine the time of work? I would say that this is (n - 1) * (n - 1) = n ^ 2 - 2n - 1 = O (n ^ 2).

I'm not quite sure how to work with the if loop.

Answer 1

yes O (n ^ 2), just sum the number of iterations in the inner loop:

n + (n - 1) + (n - 2) + ... 1 = [ n x (n + 1) ] / 2

and if it is not a cycle, it is a management structure. usually you just count the number of times a condition is checked without considering the condition. The condition may be important if there is another loop in the if body.

how to calculate iterations of the inner loop:

• i = 0 n ,
• i = 1 n - 1 ,
• i = 2 n - 2 ,
• ....
• i = n - 2 1 times
• i = n - 1 0

, , :

n + (n - 1) + (n - 2) + ... 1 = [ n x (n + 1) ] / 2

Answer 2

@perreal :

n*(n+1)/2 => O(n^2)

"" . ( , )

, , c1, x = x + 1 c2.

(c1 | c1+c2)* n*(n+1)/2 

,

( ^ 2)

Answer 3

, , " O(n^2)", , .

, . if A[i] > A[j]: , , .

2*(n-1)*(n-1) , , :

2(n + (n-1) + ... + 1) = n(n+1) = O(n^2)

O -notation, , ( , ). :

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