Take the 2-minute tour ×

Currently, my best effort has resulted in complexity O(log[n]^2):

int power(x,n)
  int mult=1, temp=x, i=1, j=1;
  while (n>1)
    for (i=1;i<=log[n];i++)
  if (n==1)
    return (mult*temp);
  return (mult);

P.S Thank you funkymushroom for helping me with my bad English :)

share|improve this question

2 Answers 2

up vote 5 down vote accepted

The idea behind implementing this operation in logarithmic time is to use the following (mathematical) equivalences (here n/2 denotes integer division):

x^0 = 1

x^n = (xn/2)2, if n % 2 == 0

x^n = x*(xn/2)2, if n % 2 == 1

This can easily be implemented recursively according to:

int power(int x, int n) {
    if (n == 0) {
        return 1;
    } else {
        int r = power(x, n / 2);
        if (n % 2 == 0) {
            return r * r;
        } else {
            return x * r * r;

An implementation such as this will yield a O[log(n)] complexity since the input (the variable n) is halved in each step of the recursion.

share|improve this answer
Thanks! sorry I cant vote up yet.. –  user1026554 Nov 2 '11 at 22:50

What you need is to use repeated squaring. Check this out

share|improve this answer

Your Answer


