How you will compute $x^{n}$?
The first solution that we may think of is a brute force approach which is multiplying x, n times. Time complexity of this solution is $\Theta (n)$.
int fun(n)
{
int ans=1;
for(int i=1;i<=n;i++)
ans=ans*x;
return ans;
}
Can we do better? Can you reduce the time complexity of this problem?
The answer is yes and the solution is given in question 6.
This method is known as Exponentiation_by_squaring or Binary_exponentiation.
Algorithm: Exponentiation by squaring - Wikipedia | Binary Exponentiation - Competitive Programming Algorithms (cp-algorithms.com)
The time complexity of this solution is $O(\log n).$ That is the significance of this algorithm.