Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Math Topics » discretemath

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

Advanced Search

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

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)
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.



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

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.