Respuesta :
Answer:
Following are the solution to this question:
Explanation:
[tex]x^n[/tex] could be approximated by getting a small n loop as well as multiplying x for each incarnation in a linear time. It's very simple. Its key concept is to do it in log2n time.
[tex]x^n = x^{\frac{n}{2}}\ is \ obvious \ \ x^{\frac{n}{2}}[/tex]
Therefore,[tex]x^{n}, x^{\frac{n}{2}}[/tex] could be determined and divided by itself instead of [tex]x^n[/tex] calculation. It must be done frequently to ensure which half the research is done out with each stage.
Runtime:
Its repetition relationship of the above function is:
[tex]T(n) = T(\frac{n}{2}) + 1[/tex]
This can be resolved by master theorem, so it's obvious. The running time of this repeating ration, by master theorem, is [tex]O ( \log_2n )[/tex].
Pseudocode:
int exponent( int x_1, int y_1 )//defining a method exponent
{
if(y_1==1) //use if to check n value equal to 1
{return x_1;} //return x value
Int t= exponent(x_1,y_1/2);//call method
return t*t;//calculate square
}
