Recurrsive Algorithm

2. The following algorithm PoT takes as input an integer n 2 0 and outputs the decimal expansion of 2"1. (For two n-digit numbers A, B, you can assume that multiplyKS(A, B) returns their product in O(n1 38) time and Add(A, B) returns their sum in O(n) time.) PoT(n: non-negative integer) 1, if n = 0 then 2.return 1 3. P = Por(n/2]) 4. VV= multiplyKS(PP) 5. if n is even then 6. return W 7. if n is odd then //Note that when n is even, [n/2]-n/2 //Note that when n is odd. Ln/2_ (n-1)/2 return Add(w,W) (a) Compute the Big-O runtime of PoT (b) Prove PoT(n) correctly returns the decimal exansion of 2n for any n 2 0. You may assume that multiplyKS and Add are correct