Q16MCQ1 mark, −0.33The recurrence relation capturing the optimal execution time of the Towers of HanoiTowers \ of \ HanoiTowers of Hanoi problem with nnn discs is(A)T(n)=2T(n−2)+2T(n) = 2T(n − 2) + 2T(n)=2T(n−2)+2(B)T(n)=2T(n−1)+nT (n) = 2T(n − 1) + nT(n)=2T(n−1)+n(C)T(n)=2T(n/2)+1T (n) = 2T(n/2) + 1T(n)=2T(n/2)+1(D)T(n)=2T(n−1)+1T (n) = 2T(n − 1) + 1T(n)=2T(n−1)+1Sign in to save attempts.Show answer← PreviousNext →SolutionsDiscussionLoading…Sign in with Google