Yes, it=E2=80=99s definitely log base two. So if we have 4 elements the =
depth was 3. That comes from log=E2=82=82(4)+1 =3D 2+1 =3D 3.

For 8 elements, it=E2=80=99s log=E2=82=82(8)+1 =3D 3+1 =3D 4.

For 16 elements it=E2=80=99s 5.

To be really precise, when the size of the list is not a power of two yo=
u may need to round it up throw in a ceiling somewhere, like ceiling(log=E2=
=82=82(N))+1.

CL

Ruben Safir ruben-at-mrbrklyn.com=
writes:

I=E2=80=99m looking at the tutorial for merge sort and it says

=E2=80=9CSo we see that for an array of four elements, we have a tree of=
depth three. Now let=E2=80=99s say we doubled the number of elements in th=
e array to eight; each merge sort at the bottom of this tree would now have=
double the number of elements =E2=80=93 two rather than one. This means we=
=E2=80=99d need one additional recursive call at each element. This suggest=
s that the total depth of the tree is log(n) + 1, the number of times we ne=
ed to halve the number of elements in the array to reach the base case.=E2=
=80=9D

Why the log(n) + 1? this is not obvious to me. I assume this means log b=
ase 2?

=E2=80=93 So many immigrant groups have swept through our town that Broo=
klyn, like Atlantis, reaches mythological proportions in the mind of the wo=
rld - 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/reso=
urces - Unpublished Archive http://www.coinhangout.com - coins! http://www.=
brooklyn-living.com

Being so tracked is for FARM ANIMALS and and extermination camps, but in=
compatible with living as a free human being. -RI Safir 2013 ______________=
_________________________________ Learn mailing list Learn-at-nylxs.com http:/=
/lists.mrbrklyn.com/mailman/listinfo/learn