CODEWITHSUNDEEP
javaalgorithmtime-complexitybig-o
super.t
super.t

Reputation: 2736

Complexity of exponentiation algorithm

Given double x and positive int y I need to find x^y assuming the input will not cause an overflow.

I came up with an algorithm that uses the following facts about x^y:

  1. x^y=(x^floor(y/2))^2 if y is even.
  2. x^y=x*(x^floor(y/2))^2 if y is odd.
  3. x^y=1 if y is 0

The implementation:

public static double power(double x, int y) {
    if(y==0)
      return 1;

    double z=power(x, y>>>1);
    z*=z;
    if((y&1)==1)
      z*=x;

    return z;
  }

I'm somewhat struggling with its complexity analysis. There're log_2(y) recursion levels and no branching. At each level the algorithm squares z, the multiplication complexity is O(n^2) where n is the number of bits in z. We assume that no overflow can happen, hence n is at most half of that in the double type. Do I count this multiplication work as constant, which gives the algorithm's complexity of O(log_2(y))?

Upvotes: 0

Views: 907

Answers (2)

Jean Valj
Jean Valj

Reputation: 94

  1. You will do a maximum of log2(Y) loops

    • After the nth loop, y is divided n times by two at least because ​for each loop y is replaced by floor(y/2) which is lower than y/2 ​ - log2(y) is such that 2^log2(y)=y
    • you make a maximum of log2(y)+1 loop because after log2(y) loops y is replaced by floor(y/y/2)=0

  2. Each loop has a constat time of execution

  3. Therefore you will have a O(log2(y)) complexity

Upvotes: 1

Y.T.
Y.T.

Reputation: 2729

Yes the algorithm is in fact called binary exponentiation and the complexity of it is log_2(y)as you mentioned. Multiplication of two numbers will usually be considered O(1) unless the number can be arbitrarily large (also called BigInt). This is because the number of bits of a number are always constant.

Note

Also, although not entirely related to the question, I saw that you mentioned multiplication complexity is O(n) for number of n bits. This is not true. The normal way of multiplying number is actually O(n^2). But in fact we can do better than that with some fast multiplication algorithm. But that's beyond the scope of this question.

Upvotes: 5

Related Questions