From The Algorithm Design Manual Solution Wiki
Revision as of 18:52, 9 September 2020 by Algowikiadmin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

n = 1 The single element array is already its max. Loop is not entered. Max is returned

Let for n=k, the algorithm is true

For n = k+1 ,two cases arise :

1) a[k+1] is max

2) a[k+1] is not max.

If 1) holds then at the last iteration when i = k+1, m = a[k+1] is assigned. Hence max is returned

Else if 2) holds then we are left with the task of finding the max among n = k elements, which we already assumed that the algorithm does correctly.

Back to Chapter 2