For all questions below justify the answer

$($a$)$ Order the following four functions from asymptotically smallest to asymptotically largest,

indicating ties if there are any: lg$($n$!),$ lg n$,$ lg lg n$,$ n$,($n$/2)!,5^$n$,$ n$^5.$

$($b$)$ What is the worst case time complexity for binary search on a BST with n elements and

why?

$($c$)$ An algorithm takes $1$ billion times longer to process $1000$n elements than it does to process

n elements. Give a possible time complexity for this algorithm.

$($d$)$ Your co$-$worker has implemented binary search for sorted lists. Assuming a linked list

with n elements, explain why this algorithm will be slower on average than using linear

search. What is the average time complexity of this algorithm?

$($e$)$ Insertion sort is generally considered "efficient" when the array is nearly sorted. Explain

why.

$($f$)$ You are given the in$-$order and post$-$order traversals of a binary search tree:

In$-$order traversal: $[4,2,5,1,3]$

Post$-$order traversal: $[4,5,2,3,1]$

Construct and draw the binary search tree from these traversals and briefly explain your approach