Write a program to calculate pow (x,n)

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

[ad type=”banner”] [pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F*%20Function%20to%20calculate%20x%20raised%20to%20the%20power%20y%20*%2F%0Aint%20power(int%20x%2C%20unsigned%20int%20y)%0A%7B%0A%20%20%20%20if%20(y%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20else%20if%20(y%252%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20power(x%2C%20y%2F2)*power(x%2C%20y%2F2)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20return%20x*power(x%2C%20y%2F2)*power(x%2C%20y%2F2)%3B%0A%7D%0A%20%0A%2F*%20Program%20to%20test%20function%20power%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20x%20%3D%202%3B%0A%20%20%20%20unsigned%20int%20y%20%3D%203%3B%0A%20%0A%20%20%20%20printf(%22%25d%22%2C%20power(x%2C%20y))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

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.

[pastacode lang=”c” manual=”%2F*%20Function%20to%20calculate%20x%20raised%20to%20the%20power%20y%20in%20O(logn)*%2F%0Aint%20power(int%20x%2C%20unsigned%20int%20y)%0A%7B%0A%20%20%20%20int%20temp%3B%0A%20%20%20%20if(%20y%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20temp%20%3D%20power(x%2C%20y%2F2)%3B%0A%20%20%20%20if%20(y%252%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20temp*temp%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20return%20x*temp*temp%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Time Complexity of optimized solution: O(logn)
Let us extend the pow function to work for negative y and float x.

[ad type=”banner”] [pastacode lang=”c” manual=”%2F*%20Extended%20version%20of%20power%20function%20that%20can%20work%0A%20for%20float%20x%20and%20negative%20y*%2F%0A%23include%3Cstdio.h%3E%0A%20%0Afloat%20power(float%20x%2C%20int%20y)%0A%7B%0A%20%20%20%20float%20temp%3B%0A%20%20%20%20if(%20y%20%3D%3D%200)%0A%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20temp%20%3D%20power(x%2C%20y%2F2)%3B%20%20%20%20%20%20%20%0A%20%20%20%20if%20(y%252%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20return%20temp*temp%3B%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(y%20%3E%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20x*temp*temp%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20(temp*temp)%2Fx%3B%0A%20%20%20%20%7D%0A%7D%20%20%0A%20%0A%2F*%20Program%20to%20test%20function%20power%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20float%20x%20%3D%202%3B%0A%20%20%20%20int%20y%20%3D%20-3%3B%0A%20%20%20%20printf(%22%25f%22%2C%20power(x%2C%20y))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]