MESSAGE
| DATE | 2015-05-05 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [LIU Comp Sci] Examination Question for Allogorthims
|
From owner-learn-outgoing-at-mrbrklyn.com Tue May 5 18:44:15 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 938071612DF; Tue, 5 May 2015 18:44:15 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 80DDE1612E6; Tue, 5 May 2015 18:44:15 -0400 (EDT)
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id DB5E11612DF
for ; Tue, 5 May 2015 18:43:51 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 0D0F01262B
for ; Tue, 5 May 2015 18:43:50 -0400 (EDT)
Message-ID: <554947A6.4040501-at-panix.com>
Date: Tue, 05 May 2015 18:43:50 -0400
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: learn-at-nylxs.com
Subject: [LIU Comp Sci] Examination Question for Allogorthims
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com
What does this mean for the Fibonacci question?
from wikipeda
https://en.wikipedia.org/wiki/Fibonacci_heap
However at some point some order needs to be introduced to the heap to
achieve the desired running time. In particular, degrees of nodes (here
degree means the number of children) are kept quite low: every node has
degree at most O(log n) and the size of a subtree rooted in a node of
degree k is at least Fk + 2, where Fk is the kth Fibonacci number.
|
|
