use List::Util qw(min max);

@A = (53, 30, 12, 34, 65, 23, 21, 1, 23, 19);

$min=&min(@A);
$max=&max(@A);

print "$min, $max \n\n";
[download]

sub min_max (\@) {
  my $min = my $max = $_[0][0];
  for (@{ $_[0] }[1 .. $#{ $_} ]) {
    $_ < $min and $min = $_, next;
    $_ > $max and $max = $_;
  }
  return ($min,$max);
}
[download]

Actually mine is (3n/2)+2, BUT doing this recursivly is a poor choice .. It is an assignment for class ... I have a algorithum almost identical to yours, that i use for production at work ... but that isn't a luxury right now. thanks for pointing out the 1 ... using too many different languages right now and getting cnfused :) although it still prints out the same results ... I don't think it is recursing properly to all values of the array.

Hmm, upon further inspection your algorithm is the following:

sub divide {
  my $mid = @_/2;
  $ITER++;
  return if @_ == 1;
  divide(@_[0 .. $mid - 1]);
  divide(@_[$mid .. $#_]);
}

for (10 .. 30) {
  $ITER = 0;
  divide(1 .. $_);
  printf "%2d  %2d\n", $_, $ITER;
}
[download]

The order of this is N, really. Specifically, it's 2*N-1. T(N) is the time it takes to call divide() for a list of N values:

T(1) = 1
T(2) = 1 + 2*T(1)
T(4) = 1 + 2*T(2)
    ...
T(N) = 1 + 2*T(N/2)
[download]

We can then expand backwards from the generality:

T(N) = 1 + 2*T(N/2)
     = 1 + 2*(1 + 2*T(N/4))
     = 1 + 2 + 4*T(N/4)
-->  = 3 + 4*T(N/4)
     = 3 + 4*(1 + 2*T(N/8))
     = 3 + 4 + 8*T(N/8)
-->  = 7 + 8*T(N/8)
     = 7 + 8*(1 + 2*T(N/16))
     = 7 + 8 + 16*T(N/16)
-->  = 15 + 16*T(N/16)
[download]

The general equation here is T(N) = 2^k - 1 + 2^k * T(N / 2^k). We will make the following substitution: k = log(N) (base 2). We now have:

T(N) = 2^k - 1 + 2^k * T(N / 2^k)
     = 2^(log N) - 1 + 2^(log N) * T(N / 2^log(N))
     = N - 1 + N * T(N/N)
     = N - 1 + N * 1
     = 2*N - 1
[download]



$_="goto+F.print+chop;\n=yhpaj";F1:eval

my ($Min,$Max)=(sort @A)[0,-1];
[download]

Yes, for larger datasets.

My first gut-level feel for "speed of algorithms" comes from my "how much entropy did you undo with that calculation?". In this case, besides knowing the minimum and maximum, you also knew (at one point, before you threw it away) the second-smallest, third-smallest, on up to the second-largest. It must have taken time to calculate those, so you've wasted time to calculate things that don't affect the outcome.

Note that this is just for "back of the thumbnail" calculations. I've been wrong using this method, but I'm not a theoretical mathematician... I'm a hacker. {grin}

-- Randal L. Schwartz, Perl hacker

I would settle for people simply giving full disclosure. The problem I've seen with homework questions in the past is twofold:
1. Homework often introduces one or more artificial constraints to the question and answer. "Find the min using recursion". Huh? Why recursion? So we don't know if the person knows that this isn't the best way to do something, and spend a lot of time mis-answering.
2. Yes, it's possible that what we are saying is keeping a person from doing their own learning. Handing them a fish instead of teaching them to fish. Yuck. Anti-ethical, in my book.
So, as long as someone says "homework question", I'm OK with people helping, but not if it's covert.

-- Randal L. Schwartz, Perl hacker

Solved ... Slightly Round about .. but good enough for my 
class. I relise that this is very sloppy, scope wise and 
the way variables are being passed, but it works :)

thanks all who provided help.

sub Partition {

    ($A, $lower, $upper, my $min, my $max, $from) = @_;

    $n = $upper - $lower + 1;
    if ($n == "2") {
        if ($$A$lower < "$$A$upper") {
            $min = $$A$lower if $$A$lower < $min;
            $max = $$A$upper if $$A$upper > $max;
            $counter++;
        }
        elsif ($$A$upper < "$$A$lower") {
            $min = $$A$upper if $$A$upper < $min;
            $max = $$A$lower if $$A$lower > $max;
            $counter++;
        }
        return ($min,$max);
    }
    if ($upper <= "$lower") { 
        return ($min, $max);
    }
    
    $mid = int(($upper - $lower) / 2) + $lower;
    if ($$A$mid < "$min") {
        $min = $$A$mid;
        $counter++;
    }
    elsif ($$A$mid > "$max") {
        $max = $$A$mid;
        $counter++;
    }

    ($min, $max) = Partition($A,$lower,$mid,$min,$max,"part_1");
    ($min, $max) = Partition($A,$mid + 1,$upper2,$min,$max,"part_2");
    return($min,$max);
}

@A = (153, 1, 12, 65, 60, 214, 5, 21, 23, 19);

    $length = @A - 1;
    $mid    = 4;
    $min    = $A$mid;
    $max    = $A$mid;
    $min1   = $min;
    $max1   = $max;
    $mid1   = $mid;
    $upper2 = $mid;
    $counter = 0;

    ($min2, $max2) = Partition(\@A,0,$mid1,$min,$max,"main_1");
    $upper2 = $length;
    ($min3, $max3) = Partition(\@A,$mid1 + 1,$length,$min1,$max1,"main_2");

    if ($min2 < $min3) {
        $min = $min2;
    }
    else {
        $min = $min3;
    }
    if ($max2 > $max3) {
        $max = $max2;
    }
    else {
        $max = $max3;
    }