Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Algorithm to calculate power(k,n).

Objec­tive:  Given two num­bers ‘k’ and ‘n’. Write an algo­rithm to cal­cu­late kn.
Exam­ple:

k = 4, n = 5
kn = 45 = 1024

k = 2, n = 3
kn = 23 = 8

Approach:

Method 1: Brute Force

Use for loop to iter­ate from 1 to n and do k*k for each iteration.

Time Com­plex­ity: O(n)

Code:

Method 2: Only if ‘k’ and ‘n’ are pos­i­tive.

1.     Use recursion.

2.     Divide the prob­lem into sub prob­lems with size n/2 and solve it recursively.

3.     Han­dle the case if n is odd. Mul­ti­ply the final result with k.

Time Com­plex­ity: O(logn)

Exam­ple:

24 = 22 * 22 = 4*4 = 16.
So instead of doing it 2*2*2*2, we have divided into two parts = 22 * 22

Code:

Method 3: Han­dle the case if n is negative

1.     Same as Method 2 above.

2.     Instead of mul­ti­ply­ing with k, divide with k.

3.     See the code for more understanding.

Time Com­plex­ity: O(logn)

Code:

Out­put:

4 power -2 :  Result: 0.0625

You may also like...