$(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 $n$ 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 $(n-2)$ smallest disks on top of the stack are represented as $,$ the two largest disks sit at the bottom

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

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

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

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

$(5)$: Recursively, move the stack of $(n-2)$ disks $$ from B to D$,$ using A and C 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 $O$ notation.

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