# Help with model answer for time complexity

Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n?

I tried to write this in python to understand when it would be n-1 and the answer is always n. I am assuming that the loop counter in pseudo-code is evaluated one more time than the body is executed as is said in the Cormen book.

My thinking is that if the length of n is 1, the loop evaluation is still tested so regardless the answer would still be n, even if the loop body itself did not run.

Max(A)

1 MaxInt = A
2 index = 2
3 while index ≤ n // Why is the best n-1 here?
4   if MaxInt < A[index]
5     MaxInt = A[index]
6   index = index+1
7 return MaxInt


I know it has to be something very simple but I cant seem to work it out as testing with 1 or 1000 the answer I get back for a count is always n-1 (0, 999) and if I assume that the loops asserts a final time that is + 1, so 0 + 1 = 1, which is n and 999 + 1 = 1000 which is n.

The loop body will be executed $$n - 1$$ times because your index variable is initially set to $$2$$ rather than $$1$$. Hence, at the start of the loop body, the values for index are from the range $$\{2, 3, ..., n\}$$, which has $$n - 1$$ elements.
• If the worst for line 3 isn, and the best for line 3 is n - 1 (according to the answer sheet), when will it actually be n then, using your example? I thought from reading the book the loop evaluation would happen one last time even when the loop body doesnt execute, so if it is n -1 (as you suggest), when is it n? – pac234 Dec 4 '20 at 16:06