$5.(40$ points$)$ The figures below illustrate an algorithm for a variant of the Tower of Hanoi game, played on $4$ posts. The goal is the same: move a stack of $\backslash ($ n $\backslash )$ disks of increasing size from one post to another, using the other two posts for temporary storage, and during the process never place a larger disk on top of a smaller one. The procedure includes five steps, with steps $(2),(3),(4)$ each comprising a single move, and steps $(1)$ and $(5)$ correspond to recursive calls.

Initially, n disks are placed on post A $.$ The $(\backslash (\backslash$mathrm$\{$n$\}-2\backslash ))$ smallest disks on top of the stack are represented as $\backslash (\backslash$boldsymbol$\{\backslash$Delta$\}\backslash ),$ the two largest disks sit at the bottom

$(1)$: Recursively, move $\backslash (\backslash$Delta $\backslash ),$ the $(\backslash ($ n$-2\backslash ))$ disks on top of the stack, from $\backslash ($ A $\backslash )$ to $\backslash ($ B $\backslash ),$ using $\backslash ($ C $\backslash )$ and $\backslash ($ D $\backslash )$ for temporary storage during the process

$(2)$: Move the second largest disk, now sitting on top of $\backslash ($ A $\backslash ),$ from $\backslash ($ A $\backslash )$ to $\backslash ($ C $\backslash )$

$(3)$: Move the largest disk, now the only disk in $\backslash ($ A $\backslash ),$ from $\backslash ($ A $\backslash )$ to $\backslash ($ D $\backslash )$

$(4)$: Move the second largest disk from $\backslash ($ C $\backslash )$ to $\backslash ($ D $\backslash ),$ to sit on top of the largest disk

$(5)$: Recursively, move the stack of $(\backslash ($ n$-2\backslash ))$ disks $\backslash (\backslash$Delta $\backslash )$ from $\backslash ($ B $\backslash )$ to $\backslash ($ D $\backslash ),$ using $\backslash ($ A $\backslash )$ and $\backslash ($ C $\backslash )$ for temporary storage during the process

a$)$ Write a recurrence relation to describe the complexity $($in terms of the number of moves$)$ of the recursive algorithm.

b$)$ Derive the solution to your recurrence relation, assume n is an even number.

c$)$ Express the solution in big $\backslash ($ O $\backslash )$ notation.

d$)$ Likewise, the problem can be solved by first recursively moving the $(\backslash ($ n$-3\backslash ))$ disks on top from $\backslash ($ A $\backslash )$ to $\backslash ($ B $\backslash ),$ then move the $3$ largest disks at the bottom from $\backslash ($ A $\backslash )$ to $\backslash ($ D $\backslash ),$ then recursively move the $\backslash (($n$-3)\backslash )$ disks from $\backslash ($ B $\backslash )$ to $\backslash ($ D $\backslash ).$ Write the recurrence relation for the complexity for this algorithm.