in reply to finding min and max of array recursivly

One problem is that you're using 1 as your lower index bound and arrays start at 0. Why do you have to do this recursively? 
sub min_max (\@) {
  my $min = my $max = $_[0][0];
  for (@{ $_[0] }[1 .. $#{ $_} ]) {
    $_ < $min and $min = $_, next;
    $_ > $max and $max = $_;
  }
  return ($min,$max);
}

[download]
I'm taking a data structures and algorithms class -- if I'm correct, I believe your recursive code is O(n log n), whereas mine is O(n).

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

Replies are listed 'Best First'.
RE: Re: finding min and max of array recursivly
by mbond (Beadle) on Sep 28, 2000 at 17:53 UTC
    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.
[reply]
      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
[reply]
[d/l]
[select]
        Unless i am mistaken somewhere (which is always possible),
T(n) = 2*T(N/2) + 2  : not + 1.. there are 2 comparisons.

the equation should simplify as follows:
let n = 2^k;

T(n) = 2^(k-1)+2^(k-1) + ... + 8 + 4 + 2
     = 2^(k-1)+21+2+4+ ... + 2^(k-2)
     = 2^(k-1)+2(2^(k-1) - 1/2-1)
     = 2^(k-1) + 2^k - 2
     = 2^(k-1)/2 + 2^k - 2
     = 3*2^k/2 - 2
     =  3n/2  -  2

not that it REALLY matters inthe grander scheme of things ...
but i think that is right ...
[reply]

In Section Seekers of Perl Wisdom