$.(5$ points$)$ Let T$($n$)$ be the running time of Jump. Give a recursive definition of T$($n$).$ Solution: T$(1)=$ a T$(2)=$ b T$(3)=$ c T$($n$)=3$T$($n$/3)+$ d $2.(3$ points$)$ What is the height of the recursion tree for T$($n$),$ assuming n is a power of $3?$ Solution: log$3($n$)13.(3$ points$)$ What is amount of work $($aka sum of the values in the nodes$)$ at level k of this tree? Solution: d$3$ k $4.(4$ points$)$ What is the big$-$Theta running time of Jump? Briefly justify your answer. Solution: The number of leaves is $3$log$3$ n$1=$ n $3,$ which is $($n$).$ The total number of nodes is proportional to the number of leaves. Since each node contains a constant amount of work, the running time is proportional to the number of nodes. So the running time is $($n$).$