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$
1
  • $\begingroup$ The best case is for the smallest number of iterations ! $\endgroup$
    – user16034
    Jan 24, 2023 at 15:57

3 Answers 3

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, 2020 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, 2020 at 16:06
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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