Consider the following recursive algorithm to compute x^n power( x, n) { if (n == 0)...

 

Transcribed Image Text:

Consider the following recursive algorithm to compute x^n power( x, n) { if (n == 0) return 1; else if (n == 1) else { return x; tmp = power(x, n/2); } } if (n%2==0) return tmp*tmp; else return tmp*tmp*x; How many multiplications do we need to compute x^116 using this algorithm? Please indicate the number using digits. Hint: first write 116 in binary. Consider the following recursive algorithm to compute x^n power( x, n) { if (n == 0) return 1; else if (n == 1) else { return x; tmp = power(x, n/2); } } if (n%2==0) return tmp*tmp; else return tmp*tmp*x; How many multiplications do we need to compute x^116 using this algorithm? Please indicate the number using digits. Hint: first write 116 in binary.