Reference no: EM131240123

A number k > 1 is called humble if the only prime factors of k are 3 and 5. Consider the task of,on input n, outputting the n smallest humble numbers and the following algorithm to do it:

Humble(n)

count = 0, prevOutput = 0

Heap.Insert(3)

Heap.Insert(5)

while (count n)

cur = Heap.ExtractMin

if cur != prevOutput

then output cur

Heap.Insert(3*cur)

Heap.Insert(5*cur)

count = count + 1

prevOutput = cur

(a) Argue that the algorithm above (1) outputs numbers in increasing order, (2) doesnot output any number twice, (3) only outputs humble numbers, and (4) outputs all of thefirst n humble numbers.

(b) Derive an exact (i.e., no O-notation) bound on the number of times Heap. Insertis called.

(c) Bound exactly the number of times Heap.ExtractMin is called.(Hint: Use (b).)

(d) Use the answers to (b) and (c) above to argue that Humble runs in O(n log n)time. Assume that arithmetic can be performed in O(1) time.