Be the first user to complete this post

Add to List 
Algorithm to calculate power(k,n).
Objective: Given two numbers ‘k’ and ‘n’. Write an algorithm to calculate k^{n}.
Example:
k = 4, n = 5 k^{n}= 4^{5} = 1024 k = 2, n = 3 k^{n}= 2^{3} = 8
Approach:
Method 1: Brute Force
Use for loop to iterate from 1 to n and do k*k for each iteration.
Time Complexity: O(n)
Code:
Method 2: Only if ‘k’ and ‘n’ are positive.
1. Use recursion.
2. Divide the problem into subproblems with size n/2 and solve it recursively.
3. Handle the case if n is odd. Multiply the final result with k.
Time Complexity: O(logn)
Example:
2^{4}= 2^{2}* 2^{2}= 4*4 = 16. So instead of doing it 2*2*2*2, we have divided into two parts = 2^{2}* 2^{2}
Code:
Method 3: Handle the case if n is negative
1. Same as Method 2 above.
2. Instead of multiplying with k, divide with k.
3. See the code for more understanding.
Time Complexity: O(logn)
Code:
Output:
4 power 2 : Result: 0.0625