Time Complexity of Efficient way to find power of a number

Question

I have written a small piece of code to find the power of a number

Can any one tell me how to find the time complexity of this code. and what is the time complexity of this code. and is it a efficient way to find powers of a number

the code is :

public static void main(String[] args) {

        System.out.println(optPower(7, 15));    
    }

    static int optPower(int x, int y) {
        // divide in buckets

        if (y == 0) {
            return 1;
        }
        if (y == 1) {
            return x;
        }
        if (y == 2)
            return x * x;

        int tmpY;

        boolean isYmodified = false;
        if (y % 2 == 0) {
            tmpY = y;
        } else {
            tmpY = y - 1;
            isYmodified = true;
        }

        int biggestBucket = 2;
        int n = biggestBucket;

        /*
         * tmpY/4 , here '4' can be used as a tweking parameter to size the
         * buckets
         */
        while (tmpY % n == 0 && tmpY / 4 >= n) {
            biggestBucket = n;
            n = n * 2;
        }

        int res = 1;
        for (int i = 0; i < biggestBucket; i++) {
            res = res * x;
        }

        int mul = res;
        for (int j = 1; j < tmpY / biggestBucket; j++) {
            mul = mul * res;
        }

        return isYmodified ? mul * x : mul;

    }

As requested, I have added more notes for clearer explanation of the algorithm.

if I want to compute 5 raise to 16

step 1:-

5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5

here x=5, y=16 in the above method

if y is odd we multiple an extra x in the final result and assign tmpY as y-1 to make it even

so noOfBuckets = 4 because of below code

while (tmpY % n == 0 ) {
        biggestBucket = n;
        n = n * 2;
    }
    that is 
 16/(2 raise to 2)

step 2:-

divide 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5 into 4 buckets
bucket1 :- 5,5,5,5
bucket2 :- 5,5,5,5
bucket3 :- 5,5,5,5
bucket4 :- 5,5,5,5

step 3:- compute bucket 1 only and use the result of this bucket for remaining buckets result of bucket 1 = 625 = 5*5*5*5

step 4 :-enter code here final result is bucket1*bucket1*bucket1*bucket1 i.e 625 * 625 * 625 * 625 i.e. 5 raise to 16

then we are avoiding iterations in bucket 2,3,4 and directly using the value from bucket 1 to get to the final result.

See http://stackoverflow.com/a/11032063/1002790 and http://stackoverflow.com/a/14396503/1002790 — Salih Erikci, Nov 05 '14 at 13:34
I don't understand what your code is doing. Why are you using buckets to compute a power? It would be helpful if you added comments in the code that more clearly explains what each step is doing. — Mike Ounsworth, Nov 05 '14 at 13:34
I'd say the time complexity is `O(biggestBucket + y / biggestBucket)` :D — Olavi Mustanoja, Nov 05 '14 at 13:39
Hello Mike Ounsworth, I have added a few more clarifications to the code. please see if it helps — Argho Chatterjee, Nov 05 '14 at 14:02
did my last edit help anybody understand the algorithm that i have prescribed. Can any one suggest how to calculate the power of a number in log n time — Argho Chatterjee, Nov 05 '14 at 14:06
"Can any one suggest how to calculate the power of a number in log n time". Your code does that. — Luminous, Nov 05 '14 at 15:04
So In short, if we want to write a algorithm in log n time space, then we need to follow the binary tree search approach always? i mean to say that divide the problem in smaller problems and then only solve that small problem? without computing all the elements and then mearge the result to get to the solution, is this what we call solving in log n time space .? — Argho Chatterjee, Nov 05 '14 at 15:20
No, it depends on what your problem is. It depends. log(n) time complexity means there are n time slices that will solve your problem. As n grows, your time complexity grows linearly. Your method of achieving log(n) time complexity does not reflect how all methods that are also log(n) are achieved. — Luminous, Nov 05 '14 at 18:15

score 2 · Accepted Answer · answered Nov 05 '14 at 14:21

2

The square-and-multiply method takes time O(log n):

function power(b, e)
    if (e == 0) return 1
    if (e is even) return power(b*b, e/2)
    /* e is odd */ return b * power(b, e-1)

answered Nov 05 '14 at 14:21

user448810

17,381
4
34
59

Olavi Mustanoja · Answer 2 · 2014-11-05T14:20:42.713

0

With the assumption that your code works with exponents other than powers of 2, then indeed your code runs in O(log n) time

edited Nov 05 '14 at 14:20

answered Nov 05 '14 at 13:54

Olavi Mustanoja

2,045
2
23
34

I have a query..in my code, i am reducing the number of multiplications that is done, that is I am reducing it to the bucket size. then using the bucket result to compute the results for other buckets. can u please help me solve this in log(n) time complexity..... – Argho Chatterjee Nov 05 '14 at 14:00

Time Complexity of Efficient way to find power of a number

2 Answers2