$($d$)$ The recurrence relationship for the worst case time complexity in MergeSort is given by:

W$($n$)=2$W$($n$/2)+$ n $1$ for n$>1$

W$(0)=$ W$(1)=0$

Assuming that n$=2$k $,$ for some integer k$,$ use back substitution to show that this

recurrence leads to an expression of the form:

W$($n$)=2$k W$($n$/(2$k$))+$ n $-2$k$-1+$ n $...-22+$ n $-2+$ n $-1$

Then solve this recurrence to prove that the worst case time complexity for MergeSort is O$($n log$2$ n$).$