This is my second attempt at getting this question answered...please answer the question appropriately: Please solve the attached question for BIG-THETA (and also give the recurrence for T(n). I would like to have this shown through the use of a recurrence tree. Also, this has already been answered on here, but please do not just copy that answer (I will leave negative feedback if it is copied from the other answer). I would like to have more explenation as to how you came up with the recurrence formula, also as to why the longest path is the rightmost one, as well as why the height is calculated to be ((2/3)^k)n=1. Please solve this in as much detail as possible to receive feedback. I am trying to learn this material, not just necessarily looking for only the answer. Thank you in advance

Problem 3. Let T(n) be the running time of ALG1 called for l 0 and r n 1. Write the recurrence for T(n), solve it and give a big-Theta bound. ALG 1 (A,l,r) input: array ALl..r] l if T l then return 0 2 0, n r-l +1 3 for i l to r A i 5 s ALG 1 (A, i, r n/3) 6 st ALG 1 (A, l n/3, r) return