Question 1 Part a)
CSC263 – Assignment 2
Cristyn Howard Monday, January 29, 2018
• Let α(n) denote the number of 1’s in the binary representation of n.
• Lemma: based on the structural definition of binary forests, a binary forest with n nodes contains α(n) trees.
• Lemma: a tree with n nodes contains n − 1 edges.
• Let the trees in a binary heap with n nodes be labelled Gi, where 1 ≤ i ≤ α(n), and let ki denote the number of nodes in tree Gi.
• Weknowthatα(n)ki =n,sothenα(n)(ki−1)=n−α(n).
i=1 i=1
• Thus we can conclude that a binary heap with n nodes contains n − α(n) edges. Part b)
• Binomial heap H has n nodes and n − α(n) edges before any insertions.
• After k insertions, H has n+k nodes and (n+k)−α(n+k) edges.
• The number of edges created by k insertions is thus [(n+k)−α(n+k)]−[n−α(n)] = n+k−α(n+k)−n+α(n) = k + α(n) − α(n + k).
– Notethatα(n+k)≥0,andsok+α(n)−α(n+k)≤k+α(n). – Further, note that α(n) ≤ ⌊log2 n⌋ + 1 (by the definition of α(n)). – Soalltogetherwehavek+α(n)−α(n+k)≤k+⌊log2n⌋+1.
• Pairwise comparisons between node values (which occur in constant time) take place whenever an insertion of an element into H creates a new edge, as the newly connected nodes must be compared and potentially swapped to preserve the heap order property.
• The dominant factor affecting the worst case running time of inserting k elements into H is the number of comparisons that must occur, or the number of edges that must be created, which we know is bounded above by k + ⌊log2 n⌋ + 1.
• When k < log2 n, the dominant term in [k + ⌊log2 n⌋ + 1] is log2 n, so the worst case running cost of inserting k elements into H is O(log2 n).
• However when k > log2 n, the dominant term in [k + ⌊log2 n⌋ + 1] is k, so the worst case running cost of inserting k elements into H is O(k), and the average cost of inserting 1 element is O(k/k), or O(1).
1
Question 2
• The wrapper function contains only constant time operations (besides the call to check-bal).
• Base case inputs to check-bal that trigger no recursive calls (x = leaf, x = NIL) contain only constant time
operations.
• In non-base cases (when x has at least one child), all operations that are not recursive calls (evaluating if conditions, doing arithmetic operations, executing return statements) occur in constant time.
• Then the dominant factor in the running time is the number of recursive calls.
• Whenever x has one child, check-bal is called on that child, and whenever x has two children, check-bal is structured to call on both of them. So check-bal is structured to call recursively on all nodes of the subtree rooted at x.
• When x is the root of a 2-balanced BST (no recursive calls to check-bal return FALSE), we know that check-bal is called recursively on all nodes of the BST, thus there exists an input ∀n ∈ N where check-bal is called n times. So T ∈ Ω(n).
• Check-bal is called at most once per node, therefore the maximum number of check-bal calls for a BST of size n∈Nisn. SoT ∈O(n).
• Thus the worst case running time of this algorithm is Θ(n), where n is the # of nodes in the BST rooted at u. 2