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

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

//code

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;

    else

        return x * temp * temp;

}

 public static void main(String [] args)

{

int res=power(2,3);

System.out.println(res);

}

}

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

Thanks