3. (3 pt) Consider the following recursive function that solves the Tower of Hanoi puzzle (https://www.mathsisfun.com/games/towerofhanoi.html). Note that n is the number of disks; from, to and intermediate are the names of the three rods: public static void solveHanoi(int n, char from, char to, char intermediate) if (n== 0) return; solveHanoi(n-1, from, intermediate, to); System.out.println("Move one disk from " + from + " peg to the " + to + " peg"); solveHanoi(n-1, intermediate, to, from); (a) Give a recurrence relation T(n) that describes the running time of this recursive function (give both base and recursive cases) (1 pt) (b) Solve the recurrence relation to get running time by using the repeated substi- tution method (2 pt)