Fast Exponentiation Power in Log N in DSA Java - Execution Trace

Concept Flow - Fast Exponentiation Power in Log N

Start with base and exponent

↓

Is exponent 0?

Yes→Return 1

No↓

Recursively compute power(base, exponent/2)

↓

Square the half power result

↓

Is exponent odd?

Yes→Multiply by base

No↓

Return final result

This flow shows how the power function reduces the exponent by half each step, squares the result, and multiplies by base if exponent is odd, achieving fast calculation.

Execution Sample

DSA Java

public static int power(int base, int exp) {
    if (exp == 0) return 1;
    int half = power(base, exp / 2);
    int result = half * half;
    if (exp % 2 != 0) result *= base;
    return result;
}

Calculates base raised to exp using recursion and squaring to reduce time complexity to O(log n).

Execution Table

Step	Operation	Exponent (exp)	Half Power Result	Multiply by Base?	Result	Call Stack Depth
1	Call power(2,5)	5	-	Check if odd	-	Depth 1
2	Call power(2,2)	2	-	Check if odd	-	Depth 2
3	Call power(2,1)	1	-	Check if odd	-	Depth 3
4	Call power(2,0)	0	-	Return 1	1	Depth 4
5	Return from power(2,0)	0	1	No	1	Depth 4 to 3
6	Calculate half*half for exp=1	1	1	Yes	2	Depth 3
7	Return from power(2,1)	1	2	Yes	2	Depth 3 to 2
8	Calculate half*half for exp=2	2	2	No	4	Depth 2
9	Return from power(2,2)	2	4	No	4	Depth 2 to 1
10	Calculate half*half for exp=5	5	4	Yes	32	Depth 1
11	Return from power(2,5)	5	32	Yes	32	Depth 1

💡 Recursion ends when exponent reaches 0, returning 1, then results combine on return steps.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 10	Final
exp	5	0	1	2	5	5
half	-	1	1	2	4	4
result	-	1	2	4	32	32
call stack depth	1	4	3	2	1	1

Key Moments - 3 Insights

Why do we multiply by base only when exponent is odd?

Because when exponent is odd, dividing by 2 loses one factor of base. Multiplying by base restores that factor, as shown in steps 6 and 10 in the execution_table.

Why does the recursion stop when exponent is zero?

Exponent zero means base^0 which is 1. The recursion base case returns 1 at step 4, stopping further calls.

How does squaring the half power reduce time complexity?

Instead of multiplying base exp times, we compute power for half exponent once and square it, reducing calls from exp to log2(exp), as seen by call stack depth reducing from 5 to 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result returned by power(2,1) at step 7?

A 1

B 4

C 2

D 32

💡 Hint

Check the 'Result' column at step 7 in the execution_table.

At which step does the recursion reach the base case where exponent is zero?

A Step 1

B Step 4

C Step 8

D Step 10

💡 Hint

Look for the step where exponent is 0 and result is 1 in the execution_table.

If exponent was 4 instead of 5, how would the 'Multiply by Base?' column change at the final step?

A It would be 'No' because 4 is even

B It would be 'Yes' because 4 is odd

C It would be 'Yes' because 4 is even

D It would be 'No' because 4 is odd

💡 Hint

Check how 'Multiply by Base?' is set for even exponents in the execution_table.

Concept Snapshot

Fast Exponentiation (Power) in Log N:
- Use recursion to compute power(base, exp/2)
- Square the half power result
- If exp is odd, multiply by base once
- Base case: exp == 0 returns 1
- Time complexity: O(log n) due to halving exponent each call

Full Transcript

Fast exponentiation calculates base raised to an exponent quickly by reducing the exponent by half each recursive call. When the exponent reaches zero, it returns 1. Each recursive call computes power for half the exponent, squares it, and if the original exponent was odd, multiplies by the base once more. This reduces the number of multiplications from linear to logarithmic in the exponent size, making it efficient for large powers.

Practice

1. What is the main advantage of using fast exponentiation (power) in log N time compared to the simple method of multiplying the base n times?

easy

A. It uses less memory by storing all intermediate powers

B. It reduces the number of multiplications from n to about log n

C. It works only for positive exponents

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand simple exponentiation

   Simple method multiplies the base by itself n times, so it does n multiplications.

2. Step 2: Understand fast exponentiation advantage

   Fast exponentiation uses repeated squaring, reducing multiplications to about log n times.

3. Final Answer:

   It reduces the number of multiplications from n to about log n -> Option B

4. Quick Check:

   Fast exponentiation = fewer multiplications [OK]

Hint: Fast exponentiation halves exponent each step [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Assuming it only works for positive exponents
• Confusing memory use with speed

2. Which of the following Java method signatures correctly represents a fast exponentiation function that calculates base^exponent?

easy

A. int power(int base)

B. static void power(int base, int exponent)

C. public int power(int base, int exponent, int mod)

D. public static int power(int base, int exponent)

Solution

1. Step 1: Check method return type

   Power function returns an int result, so return type should be int.

2. Step 2: Check method parameters and modifiers

   Method should accept base and exponent as int, be static for utility use, and public for access.

3. Final Answer:

   public static int power(int base, int exponent) -> Option D

4. Quick Check:

   Correct signature = public static int power(int base, int exponent) [OK]

Hint: Power method returns int and takes base, exponent [OK]

Common Mistakes:

• Using void return type
• Missing static keyword
• Wrong number of parameters

3. What is the output of the following Java code snippet?

public class Test {
  public static int power(int base, int exponent) {
    if (exponent == 0) return 1;
    int half = power(base, exponent / 2);
    if (exponent % 2 == 0) return half * half;
    else return half * half * base;
  }
  public static void main(String[] args) {
    System.out.println(power(2, 5));
  }
}

medium

A. 32

B. 25

C. 10

D. 16

Solution

1. Step 1: Trace recursive calls for power(2, 5)

   power(2,5) calls power(2,2), which calls power(2,1), which calls power(2,0)=1.

2. Step 2: Calculate results bottom-up

   power(2,0)=1; power(2,1)=1*1*2=2; power(2,2)=2*2=4; power(2,5)=4*4*2=32.

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember 2^5 = 32, check recursion carefully [OK]

Common Mistakes:

• Confusing exponent division
• Forgetting to multiply base for odd exponent
• Incorrect base case handling

4. Identify the bug in the following fast exponentiation code and select the correct fix.

public static int power(int base, int exponent) {
  if (exponent == 0) return 1;
  int half = power(base, exponent / 2);
  if (exponent % 2 == 1) return half * half;
  else return half * half * base;
}

medium

A. Swap the if and else blocks to handle odd exponent correctly

B. Change exponent % 2 == 1 to exponent % 2 == 0

C. Add a base case for exponent == 1

D. Remove the recursive call and use a loop instead

Solution

1. Step 1: Analyze condition for odd exponent

   Current code returns half*half when exponent is odd, but it should multiply by base in that case.

2. Step 2: Fix condition blocks

   Swapping if and else blocks makes odd exponent return half*half*base and even exponent return half*half.

3. Final Answer:

   Swap the if and else blocks to handle odd exponent correctly -> Option A

4. Quick Check:

   Odd exponent multiplies extra base [OK]

Hint: Odd exponent needs extra base multiplication [OK]

Common Mistakes:

• Confusing odd/even condition
• Adding unnecessary base case
• Replacing recursion with loop without reason

5. You want to compute (3^1000) % 1000000007 efficiently using fast exponentiation. Which modification should you add to the standard fast exponentiation method to handle this correctly?

hard

A. Calculate 3^1000 first, then apply modulo once at the end

B. Use floating point arithmetic to handle large powers

C. Add modulo operation after every multiplication to keep numbers small

D. Use a loop instead of recursion to avoid stack overflow

Solution

1. Step 1: Understand modular exponentiation need

   Directly calculating 3^1000 is huge and causes overflow, so modulo must be applied during calculation.

2. Step 2: Apply modulo after each multiplication

   Adding modulo after each multiplication keeps intermediate results within integer limits and ensures correct final modulo result.

3. Final Answer:

   Add modulo operation after every multiplication to keep numbers small -> Option C

4. Quick Check:

   Modulo after multiplication prevents overflow [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Applying modulo only once at the end
• Using floating point causing precision loss
• Ignoring overflow in recursion