Analyzing an Algorithm

[vladdy19]

I need help coming up with the running time, T(n) for this algorithm

1) for i = 0 to length[A] – 1
2)      k = i + 1
3)      for j = i + 2 to length[A]
4)          if A[k] > A[j]
5)               k = j
6)      if k ≠ i + 1
7)           temp = A[i + 1]
8)           A[i + 1] = A[k]
9)           A[k] = temp

length[A]=n

I know that line 1 executes n+1 times
and line 2 executes n times
however i'm a little confused about the second for statement, the one in line 3
and how to calculate the 'if' statements
any help is appreciated, thanks

[sarehu]

One way to deal with 'if' statements is to simply take the maximum possible number of steps it could take. The comparison will take place every time, and assume the interior step will execute every time. This will give you an upper bound on the amount of execution time, but not necessarily a tight upper bound on the worst case execution time. In your example, the blocks inside the 'if' control structures each take O(1) time, so it doesn't matter -- the comparison takes O(1) time, too, after all.

You would then want to ask if the steps taken inside an 'if' block affect future computation times. In your example, there is no subsection of the code whose asymptotic complexity would change as a result of the side effects of your conditional blocks, so you'd get a tight bound.