Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



bigOh form for worstcase complexity function
Posted:
Nov 7, 2013 1:27 PM


The following pseudocode procedure implements an algorithm for determining the maximum value in an array a1, a2, a3, . . . , an of integers. Here n â¥ 2 and the entries in the array need not be distinct.
procedure Maximum (n: integer; a1,a2,a3,. . .,an: integers) begin max := a1 for i := 2 to n do if ai > max then max := ai end
a) If the worstcase complexity function f (n) for this segment is determined by the number of times the comparison ai > max is executed, find the appropriate âbigOhâ form for f.
b) What can we say about the bestcase and averagecase complexities for this implementation?
I'm simply not sure what this problem is asking for. I not asking anyone to answer this problem as it is a homework problem but I would like some direction on how to get there. Any help is appreciated.



