Algorithm complexity in for loop I have an algorithm and I would like to know how many times each line is called.
There I wrote which lines I understand and some lines is left.
j := 1   ---------------------- 1 time
while j < n do  --------------- n times
  x := B[j]    ---------------- n-1 times
  k := j    ------------------- n-1 times
  for i := j + 1 to n do  ----- ?
    if B[i] < x then     ------ ?
      x := B[i]     ----------- ?
      k := i    --------------- ?
  B[l] := B[j]   -------------- n-1 times
  B[j] := x     --------------- n-1 times
  j := j + 1   ---------------- n-1 times

Note: k := i means that line is called once but for i := j + 1 to n do - twice: assign and comparison.

Hint: You enter the for loop n-1 times as shown from the line above.  Then how many loops to you do?  It should be something like n-j, but you have to figure out the ends-there may be a +1 or -1 or something.  Does your definition of for do the loop with i=n or not?  so the for will be executed 2*(n-1)*(something like n-j) times.  Given the if statement, you can't say for sure how many times the lines within it are executed.  All you can do is find a maximum, assuming the if always evaluates as true.
