MESSAGE
DATE | 2016-11-09 |
FROM | Ruben Safir
|
SUBJECT | Re: [Hangout-NYLXS] [Learn] mergesort tutorial
|
On 11/09/2016 04:37 AM, Ruben Safir wrote: > I'm looking at the tutorial for merge sort and it says > > "So we see that for an array of four elements, we have a tree of depth > three. Now let's say we doubled the number of elements in the array to > eight; each merge sort at the bottom of this tree would now have double > the number of elements -- two rather than one. This means we'd need one > additional recursive call at each element. This suggests that the total > depth of the tree is log(n) + 1, the number of times we need to halve > the number of elements in the array to reach the base case. " > > Why the log(n) + 1? this is not obvious to me. I assume this means log > base 2? > > http://www.cprogramming.com/tutorial/computersciencetheory/mergesort.html
-- So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world - RI Safir 1998 http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002 http://www.nylxs.com - Leadership Development in Free Software http://www2.mrbrklyn.com/resources - Unpublished Archive http://www.coinhangout.com - coins! http://www.brooklyn-living.com
Being so tracked is for FARM ANIMALS and and extermination camps, but incompatible with living as a free human being. -RI Safir 2013 _______________________________________________ hangout mailing list hangout-at-nylxs.com http://www.nylxs.com/
|
|