Self Power

Computer Science Level 1

Consider the problem of calculating power $x^{n}$ where $x$ is any number, and $n$ is a positive integer. If you create your own power function, what is best possible complexity of the function?

O(n)

O(\log n)

O(n\log n)

O(\log\log (n))

2 solutions

Beakal Tiliksew
Apr 30, 2016

A recursive $O(n)$ implementation:

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

We can reduce it to $O(\log(n))$ by calculating power(x, y//2) only once at each level.

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

An alternative iterative implementation would be

int pow(int a, int p) {
    int ans = 1;
    for (; p; p >>= 1, a = a * a)
        if (p&1) ans = ans * a;
    return ans;
}

Christopher Boo - 5 years, 1 month ago

Rico Lee
May 6, 2016

Somehow I got this right. I do not do computer science at all, however, using mathematical knowledge 'n log x' is also log x^n. I guessed I started swapping the x and n around.

So, seeing as I only need one log...O(log n) is my answer. Wow.

Self Power

2 solutions

0 pending reports