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


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

9 Years
Discussion Span
Last Post by 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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.