MESSAGE
| DATE | 2016-11-09 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [Learn] mergesort tutorial
|
From learn-bounces-at-nylxs.com Wed Nov 9 04:37:48 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id 6B012161316;
Wed, 9 Nov 2016 04:37:48 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id F37B2160E77;
Wed, 9 Nov 2016 04:37:40 -0500 (EST)
To: learn-at-nylxs.com, hangout
From: Ruben Safir
Message-ID: <9bfa2486-929e-04f4-a451-155dfacabae7-at-mrbrklyn.com>
Date: Wed, 9 Nov 2016 04:37:40 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
Subject: [Learn] mergesort tutorial
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
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
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
|
|
