in reply to RE: RE: Re: finding min and max of array recursivly
in thread finding min and max of array recursivly

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 ... 
  • Comment on RE: RE: RE: Re: finding min and max of array recursivly

Replies are listed 'Best First'.
RE: RE: RE: RE: Re: finding min and max of array recursivly
by japhy (Canon) on Sep 28, 2000 at 21:19 UTC
    D'oh. Yeah. You're right. Well, we're both right. The runtime is between 2N-1 and 1.5N-2, depending on the ACTUAL number of calculations that end up needing to be done.

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