# 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[1]
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 best case is for the smallest number of iterations !
– user16034
Jan 24, 2023 at 15:57

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.

• Yes and that makes sense but line 3 is the loop evaluation? Dec 4, 2020 at 14:08
• 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? Dec 4, 2020 at 16:06

The number of iterations of the body of the loop is $$\max(0,n-1)$$.

The number of comparisons performed at line $$3$$ is $$\max(1,n)$$.

For both, best case and worst case are identical. If the answer sheet says otherwise, it is wrong.

Observe that after index is incremented from n to n+1 by line 6, the condition in line 3 is tested one last time (this condition evaluates to False because index=n+1, which is not <=n) before the while loop exists.

Line 3 is executed for the first time when index = 2, and executed for the last time when index = n + 1. Hence, the total number of times line 3 is executed is n. Lines 4-6 are executed when index takes values 2 to n, and hence are executed n-1 times.