We define the worst$-$case cost of inserting a new key into H to be the maximum number of pairwise

comparisons between keys that is required to do this insertion.

Consider the worst$-$case total cost of successively inserting k keys into H$.$ It is clear that for k $=1($i$.$e$.,$ inserting only one key$)$ the worst$-$case cost is O$($log$2$ n$).$ Show that when k $>$ log$2$ n$,$ the average cost of an insertion, i$.$e$.,$ the worst$-$case total cost of the k successive insertions divided by k$,$ is bounded above by constant.