Question

Discrete Mathematics

Time Complexity Analysis Due: May 9th, 2019 Math 4 6026 Heap Sort Another algorithm for sorting uses a specialized tree structure called a "heap." Specifically, we will use a binary heap, which is like a binary tree with hierarchy. Here is an example of a binary heap structure 1. 2. There is a top vertex, called the parent vertex (aka node). The top parent vertex connects to two vertices a level below. These vertices are the "left child" and the "right child." Each child can be a parent of zero to two children on a level below. Assign vertices left to right at each level.We are going to go step-by-step through the process of heap sort to sort the list L 3. 4. 14,8,2,6, 1]. Build the Heap First, you build a heap in the following manner: Make the oth element (4) the top vertex. 1. 4 2. Make the 1st element (8) the left child. Make the 2nd element (6) the right child. 3. 8 4. Make thed element (6) the left child's left child. 5. Make the 4th element (1) the left child's right child. What is the time complexity of building a heap from a list of size n? Explain.

Answer 1

Given $n=2^k-1=1+2+2^2+\cdots 2^{k-1}$ elements, first we place the 0-th element at the first position in the heap. This takes time O(1)

The next 2 elements (1,2) are placed at the left and right positions in the heap. Going down a height 1 takes time 1 and then adding this element takes another time 1. So total time is $2\times (1+1)$

The next 4 elements (3,4,5,6) are placed the the left-left, left-right, right-left and right-right positions respectively. This takes time $4\times (2+1)$

In general, the total time is $2^i\times (i+1)$ for the $2^i$ elements

Total time complexity is therefore $S=\sum_{i=0}^{k-1}2^{i}(i+1)=2^0(1)+2^1(2)+2^2(3)+\cdots$

Then

k-1 2S2+1) 2)22 (2)23 (3) +..

Subtracting we get

t-1

That is,

t-1

Which equals $S=2^k-2$

That is,

S = n-2-O(n)

So the time complexity is

O(n)