Question

(a) Set up a divide-and-conquer recurrence relation for the number of multiplications required to compute${\mathit{x}}^{\mathbf{n}}$, where $\mathit{x}$is a real number and $\mathit{n}$is a positive integer, using the recursive algorithm from Exercise 26 in Section 5.4.

b) Use the recurrence relation you found in part (a) to construct a big- $\mathit{O}$estimate for the number of multiplications used to compute ${\mathit{x}}^{\mathbf{n}}$using the recursive algorithm.

Short answer

a) The number of multiplications required is$f\left(n\right)=f(n/2)+2$

b) The number of multiplication required using big-O is$O\left(\log n\right)$

Step-by-step solution

Recurrence Relation and Master Theorem definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms: $\mathbf{\text{f(n)=a f(n / b)+c}}$

In MASTER THEOREM, let $\mathit{f}$be an increasing function that satisfies the recurrence relation $\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathit{a}\mathit{f}\mathbf{(}\mathit{n}\mathbf{/}\mathit{b}\mathbf{)}\mathbf{+}\mathit{c}{\mathit{n}}^{\mathbf{d}}$whenever$\mathit{n}\mathbf{=}{\mathit{b}}^{\mathbf{k}}$, where $\mathit{k}$is a positive integer, $\mathit{a}\mathbf{\ge }\mathbf{1}\mathbf{,}\mathit{b}$is an integer greater than$\mathbf{1}$, and $\mathit{c}$and $\mathit{d}$are real numbers with $\mathit{c}$positive and $\mathit{d}$nonnegative. Then $\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$is$\mathit{O}\mathbf{\left(}{\mathbf{n}}^{\mathbf{d}}\mathbf{\right)}$if $\mathit{a}\mathbf{<}{\mathit{b}}^{\mathbf{d}}\mathit{O}\mathbf{\left(}{\mathbf{n}}^{\mathbf{d}}\mathbf{logn}\mathbf{\right)}$if $\mathit{a}\mathbf{=}{\mathit{b}}^{\mathbf{d}}$and$\mathit{O}\mathbf{\left(}{\mathbf{n}}^{{\mathbf{log}}_{\mathbf{b}}\mathbf{a}}\mathbf{\right)}$ if$\mathit{a}\mathbf{>}{\mathit{b}}^{\mathbf{d}}$.

Apply Recurrence Relation

a)

We register $x^n$when $\text{n}$is even by first processing $\text{y}=x^{n/2}$recursively and afterward doing one increase, specifically$yxy$. At the point when $\text{n}$is odd, initially $\text{y}=x^{(n-1)/2}$recursively and after that do two duplications, in particular$yxyxx$.

So if $f\left(n\right)$is the number of augmentations required, expecting the most noticeably awful, and then we have basically $f\left(n\right)=f(n/2)+2$

Apply Master Theorem      

b)

By the ace hypothesis, with$a=1,b=2,c=2$, and$d=0$, we see that $f\left(n\right)$is$O\left(n^0\log n\right)=O\left(\log n\right)$.