Consider the recursively defined sequence of Fibonacci heap operations defined by the following function:

function Tall-Heap(T, h, b) 1: if h = 1 then 2: Make-Fib-Heap(T) 3: Fib-Heap-Insert(T, b) 4: else if h = 2 then 5: Make-Fib-Heap(T) 6: Fib-Heap-Insert(T, b 1) 7: Fib-Heap-Insert(T, b) 8: Fib-Heap-Insert(T, b + 1) 9: Extract-Min(T) 10: else 11: Tall-Heap(T, h 1, b + 1) 12: Fib-Heap-Insert(T, b 0.5) 13: Fib-Heap-Insert(T, b) 14: Fib-Heap-Insert(T, b + 0.5) 15: Extract-Min(T) 16: Fib-Heap-Delete(T, b + 0.5) 17: end if a) Prove by induction on h that the Fibonacci heap that results from the call Tall-Heap(F, h, b) is a chain of h b + 1 nodes. Note there are two base cases in the algorithm.

b) What is the total time required by the call Tall-Heap(F, h, b)? Justify your answer.