Power Logarithmic

 

package jan27;

public class PowerLogarithmic {
    public static void main(String[] args) {
        int x = 10;
        int n = 8;
        System.out.println(powerLogarithmic(x, n));  // EXPECTATION
    }

    /**
     * Calculates x raised to the power n using divide-and-conquer.
     *
     * Time Complexity: O(log n)
     * - Each recursive call divides the exponent by 2.
     * - So total calls = log₂(n), and constant work per call.
     *
     * Space Complexity: O(log n)
     * - Due to recursive call stack. Depth of recursion is log₂(n).
     */
    private static int powerLogarithmic(int x, int n) {
        if (n == 0)
            return 1;                                               // BASE CASE

        int x_ki_power_n_by_2 = powerLogarithmic(x, n / 2);      // FAITH
        int x_ki_power_n = x_ki_power_n_by_2 * x_ki_power_n_by_2;   // WORK

        // If exponent is odd, multiply one extra x
        if (n % 2 == 1)                                             // WORK
            x_ki_power_n = x_ki_power_n * x;

        return x_ki_power_n;
    }
}

Case	Time Complexity	Space Complexity	Explanation
Best Case	O(log n)	O(log n)	The recursion depth is reduced by half each time (divide-and-conquer).
Average Case	O(log n)	O(log n)	For any n, the algorithm divides n by 2 recursively.
Worst Case	O(log n)	O(log n)	Same as average; the number of calls grows logarithmically with n.

🔍 Summary:

• ✅ Time Complexity: O(log n) — because the function divides n by 2 in each recursive call.

• ✅ Space Complexity: O(log n) — due to recursion stack frames, each level represents a halving of n.