Power (Linear)

Question

1. You are given a number x.

2. You are given another number n.

3. You are required to calculate x raised to the power n. Don't change the signature of power function

Note-> The online judge can't force you to write the function recursively but that is what the spirit of question is.

Write recursive and not iterative logic. The purpose of the question is to aid learning recursion and not test you.

Input Format

A number x

A number n

Output Format

x raised to the power n

package jan27;

public class PowerLinear {
    public static void main(String[] args) {
        int x = 2;
        int n = 4;

        System.out.println(powerLinear(x, n)); // Expected output: 16
    }

    /**
     * Calculates x raised to the power n using linear recursion.
     *
     * Time Complexity: O(n)
     * - One recursive call per decrement of n, so n total calls.
     *
     * Space Complexity: O(n)
     * - Recursion call stack grows up to depth n.
     */
    private static int powerLinear(int x, int n) {
        if (n == 0)
            return 1; // Base case corrected to n == 0 for proper exponentiation logic

        return x * powerLinear(x, n - 1);
    }
}

Case
Time Complexity
Space Complexity
Explanation
Best Case
O(n)
O(n)
All inputs require n recursive calls; no early return or shortcut possible.
Average Case
O(n)
O(n)
On average, recursion depth is still n; no input-specific optimization.
Worst Case
O(n)
O(n)
Always makes n recursive calls, maximum call stack usage.