0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Yes and that makes sense but line 3 is the loop evaluation? $\endgroup$ – pac234 Dec 4 '20 at 14:08
  • $\begingroup$ 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? $\endgroup$ – pac234 Dec 4 '20 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.