following rules:

a$)$ Only one disk can be moved at a time.

b$)$ Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack, i$.$e$.,$ a disk can only be moved if it is the uppermost disk on a stack.

c$)$ No disk may be placed on top of a smaller disk.

The example of $n=3$ disks given below. Initially, $3$ disks are on rod A$,$ with $7$ steps, the disks are stacked on rod C$.$

The pseudo code is given below.

ToH $(n,A,B,C)$:# Move $n$ disks from $A$ to $C$ using intermediate rod $B$

if $n1$

ToH $($n$-1,$ A$,$ C$,$ B$)$ # Move the top n$-1$ disks from $A$ to $B$ using intermediate rod $C$

Move A$->$C #Move the bottom disk from $A$ to $C$

ToH $($n$-1,$ B$,$ A$,$ C$).$ # Move the previous n$-1$ disk from B to C using intermediate rod A end

What is the running time of the above algorithm?

$3.$ Solve the following recurrences using the method of your choice.

$($a$)T(n)=2T(\frac{n}{2})+n^3$

$($b$)T(n)=3T(\frac{n}{2})+nlgn$