Answer Happy

Question 16 Question 3c Let A be a recursive algorithm that takes a real number n as its input. Algorithm A recursively invokes itself times on inputn/2, for some integer k. and does not invoke itself recursively if n 1. Without the recursive calls, the runtime of algorithm A on a real number n is ©(n). 1. Suppose that k-2. How often does A invoke itself (in Theta-notation? And what is the total runtime of A? And what is the total runtime of A? 2. Suppose now that k-1. How often does A invoke itself (in Theta-notation)? 3. Suppose now that k-logn. How often does A invoke itself (in Theta-notation)? And what is the total runtime of A? Hint: Draw a recursion tree. For each question, choose from the following options: 1.0(nlog login) 2.0(m²logn) 3.0(logn) 4.0(²) 5.enlogn/log log.n) 6.0(logn) 7.0(³) 8.0(1) 9.0 (²) 10.0(n/logn) 11.0(2) 12.0(²) 13.0(²) 14.0(n) 15. () 16.0(m²) 17.0(²³ log²n) 18. (n/loglogn) 19.0(logn) 20. (²) 21. (²)