The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Math Topics » discretemath

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  

Advanced Search

Back to Topic List Back to Topic List   Topics: [ Previous | Next ]

Posts: 2
Registered: 11/7/13
big-Oh form for worst-case complexity function
Posted: Nov 7, 2013 1:27 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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)
max := a1
for i := 2 to n do
if ai > max then
max := ai

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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.