Algorithm Problem: Ways to write power functions

I’d like to share with you a few tips on interview questions. When a question is presented to you during an interview, the interviewer usually expects you to solve it in a number of different ways which eventually leads to better time complexity. For example, you first write out a solution with O(n).This indicates that you are able to solve the problem on top of your head with a more intuitive approach, sometimes a brute force approach. Then, the interviewer might ask you, can you do better? Here’s where all the magic parts come in! The goal is to generalize an algorithm that would output an better time complexity, such as divide and conquer. The time complexity now becomes O(logn)!

Let’s go over this process using power function as example! In python, you can simply type math.pow(2,3) and the answer would be 23 = 8.

How about implementing power function yourself? Note that the code below is implemented in python3.

The following code indicates a o(x) solution

def pow(n,x):

cummu = 1

for i in range(0,x): 

    cummu = cummu * n

return cummu

The following code use recursion to reduce time complexity to o(logx)

def pow_rec(n,x):

if x < 0:     

    return 1.0/ pow(n,-x) # This case handles negative power. Two negatives get canceled out

if x == 0:

    return 1

if x == 1:

    return n

else:

    if(x%2 == 0):               # When the exponent is an  **even**  number

        rec = pow_rec(n, x/2)      **#remember the output of the recursion call so that we only have to compute half of the size once** 

        return rec * rec

     else:                             # When the exponent is an  **odd**  number, we throw in that extra n to account for the odd

        rec = pow_rec(n, x/2)

        return rec * rec *  **n** 

Please don’t feel hesitate to comment or leave questions if you’d like to discuss more on this post! Together, we learn better!