program to calculate pow(x,n)

Write a program to calculate pow(x,n):-

Given two integers x and n, write a function to compute xn. We may assume that x and n are small and overflow doesn’t happen.

Input : x = 2, n = 3
Output : 8

Input : x = 7, n = 2
Output : 49

Below solution divides the problem into subproblems of size y/2 and call the subproblems recursively.

Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.

Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

Time Complexity of optimized solution: O(logn)

Let us extend the pow function to work for negative y and float x.