MESSAGE
| DATE | 2016-11-09 |
| FROM | Asia Suarez
|
| SUBJECT | Re: [Hangout-NYLXS] mergesort tutorial
|
Well I know for sure that it takes an asymptotic runtime of O(log n) to sort each subproblem and a constant time O(1) to merge each subproblem.
Something to that nature...
Sent from my iPhone
> On Nov 9, 2016, at 4: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?
>
>
> --
> 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/
_______________________________________________
hangout mailing list
hangout-at-nylxs.com
http://www.nylxs.com/
|
|
