CODEWITHSUNDEEP
algorithmperformancetime-complexitycomplexity-theory
Labbiqa
Labbiqa

Reputation: 157

Determining the time complexity

Given the following pseudo code for an 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 do I determine the running time? I would say it's (n - 1)*(n - 1) = n^2 - 2n - 1 = O(n^2).

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

Upvotes: 4

Views: 103

Answers (3)

perreal
perreal

Reputation: 97918

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 is not a loop, it is a control structure. generally you just count the number of times the condition is checked without considering the condition. The condition may be important if there is another loop in the if body.

how to count the iterations of the inner loop:

  • when i = 0 the inner loop runs n times, then ends
  • then i = 1 the inner loop runs n - 1 times, then ends
  • then i = 2 the inner loop runs n - 2 times, then ends
  • ....
  • when i = n - 2 inner loop runs 1 times
  • when i = n - 1 inner loop runs 0 times

so all we need to do is to add the number of iterations of the inner loop:

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

Upvotes: 4

Ashkan S
Ashkan S

Reputation: 11471

@perreal is totally right about the order:

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

About the "if" part, it doesn't really matter. (I write this to answer to this part)

Lets say doing checking if takes c1 time, and doing the x=x+1 takes c2 time. You will have

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

And since you can ignore the constants from the order, it is from

O(n^2)

Upvotes: 1

md5
md5

Reputation: 23699

Actually, saying "this algorithm has a O(n^2)time complexity" suggests implicitly that it's a worst case complexity.

In a naive way, you can just count the number of times each instruction is executed in the worst case. if A[i] > A[j]: might be considered as an instruction as well, so first you don't necessarily have to ask yourself when the condition is true.

2*(n-1)*(n-1) is a majorant of the number of instructions executed in the inner-most loop, and more precisely:

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

Even if it's not important with the O-notation, there are several arrays for which the condition is always true (thus these are the worst case for this algorithm). For example:

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

Upvotes: -1

Related Questions