CODEWITHSUNDEEP
pythonpython-3.xbig-o
Ashwin Sarith
Ashwin Sarith

Reputation: 79

How to calculate a power of a number with O(log n) complexity?

This is for pure understanding, but i have a code thats basically O(n), but i am unable to decipher how to change it to Olog(n), and each time i use recursion i get nlog(n) complexity.

def power(n,p):
    val = []
    for i in range(p):
        val.append(n)
    res = val
    n = 1
    for x in res:
        n*= x
    return n
print(power(2,8)) # returns 256

what i need is a code that does the exact same as this above code but it basically does it in Olog(n) as opposed to O(n)

Upvotes: 0

Views: 1257

Answers (1)

Massifox
Massifox

Reputation: 4487

This code implements power() with complexity O(log(n)):

def power(x, y): 
    if y==0: 
        return 1
    n = power(x, y // 2)  
    if y % 2 == 0: 
        return n * n 
    else: 
        if y > 0: 
            return x * n * n 
        else: 
            return (n * n) / x

Upvotes: 1

Related Questions