Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: big-Oh form for worst-case complexity function
Replies: 0

 winkylocc Posts: 2 Registered: 11/7/13
big-Oh form for worst-case 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 worst-case complexity function f (n) for this segment
is determined by the number of times the comparison
ai > max is executed, find the appropriate âbig-Ohâ form
for f.

b) What can we say about the best-case and average-case
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.