Homework $2$

Apply the DFS$-$based algorithm to solve the topological sorting problem for the following digraphs:

Considering the alphabets A$,$ B$,$ C$,$ D$,$ E$,$ F$,$ G$,$ H$,$ I, J$,$ K$,$ L$,$ M$,$ N$,$ O$,$ P$,$ Q$,$ R$,$ S$,$ T$,$ U$,$ V$,$ W$,$ X$,$ Y$,$ Z apply both mergesort and quicksort to sort the list $\text{'}{A}^{\text{'}},{?}^{\text{'}}{L}^{\text{'}},G^{\text{'}},O^{\text{'}},I^{\text{'}},I^{\text{'}},I^{\text{'}},T^{\text{'}},I^{\text{'}},I^{\text{'}}{M}^{\text{'}}$ in alphabetical order draw the tree of the recursive calls made

Find the order of growth for the solutions of the following recurrences.

a$.T(n)=4T(\frac{n}{2})+n,T(1)=1$

b$.T(n)=4T(\frac{n}{2})+n^2,T(1)=1$

c$.T(n)=4T(\frac{n}{2})+n^3,T(1)=1$

Is mergersort a stable sorting algorithm?