Problem 6.1

We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation on the BUILD-MAX-HEAP procedure:

BUILD-MAX-HEAP(A)
1 A.heap-size = 1
2 for i = 2 to A.length
3 MAX-HEAP-INSERT(A,A[i ])
a. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
b. Show that in the worst case, BUILD-MAX-HEAP' requires $\theta(n lg n)$ time to build an n-element heap.
BUILD-MAX-HEAP and BUILD-MAX-HEAP' will not always create the same heap. example A= {1,2,3} calling BUILD-MAX-HEAP will create {3,2,1} and calling BUILD-MAX-HEAP' will create {3,1,2}.

There n-1 calls to MAX-HEAP-INSERT which takes log n time hence the upper bound is $\theta n logn$
lets assume all the elements are increasing order since we are calculating the worst time. each of the element will take log i (which is the height of tree)
$$ \sum_{i=1}^n \theta(log i)$$ $$ \theta(log 1+ log 2+....log n) $$ Apply logarithm property log m+ log n = log mn $$ \theta(log (1.2...n)) $$ $$ \theta(log (n!)) $$ by stirling approximation $$ \theta(n log n)) $$ $$ \geq \Omega(n log n) $$