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