Why time-complexity of given code is O(log n)?

// here i calculate x raised to the power y in O(logn)


class x


  static int power(int x, int y)


    int temp;

    if (y == 0)

        return 1;

    temp = power(x, y / 2);

    if (y % 2 == 0)

        return temp * temp;


        return x * temp * temp;


 public static void main(String [] args)


int res=power(2,3);




At every recursive call, you are halving the exponent. So the depth of the recursion tree would be of the order of log(y). Hence the time complexity will be O(logy)

This video might help.

1 Like