Fast Exponentiation Power in Log N in DSA C++ - 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 result

↓

Is exponent odd?

Yes→Multiply by base

No↓

Return result

The flow shows how the exponent is halved each step, squaring intermediate results, and multiplying by base if exponent is odd, achieving logarithmic time.

Execution Sample

DSA C++

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;
}

Computes base raised to exp using recursion and squaring to reduce steps to log(exp).

Execution Table

Step	Operation	Exponent	Recursive Call	Result Computed	Visual State
1	Call power(2, 10)	10	power(2,5)	Pending	Start with base=2, exp=10
2	Call power(2, 5)	5	power(2,2)	Pending	Recursion deeper, exp=5
3	Call power(2, 2)	2	power(2,1)	Pending	Recursion deeper, exp=2
4	Call power(2, 1)	1	power(2,0)	Pending	Recursion deeper, exp=1
5	Call power(2, 0)	0	None	1	Base case reached, return 1
6	Return from power(2,0)	0	None	1	Return 1 to power(2,1)
7	Compute half*half for exp=1	1	None	1*1=1	Square of half=1
8	Exponent odd, multiply by base	1	None	1*2=2	Multiply by base=2
9	Return from power(2,1)	1	None	2	Return 2 to power(2,2)
10	Compute half*half for exp=2	2	None	2*2=4	Square of half=4
11	Exponent even, no multiply	2	None	4	Return 4 to power(2,5)
12	Return from power(2,2)	2	None	4	Return 4 to power(2,5)
13	Compute half*half for exp=5	5	None	4*4=16	Square of half=16
14	Exponent odd, multiply by base	5	None	16*2=32	Multiply by base=2
15	Return from power(2,5)	5	None	32	Return 32 to power(2,10)
16	Compute half*half for exp=10	10	None	32*32=1024	Square of half=1024
17	Exponent even, no multiply	10	None	1024	Final result computed
18	Return from power(2,10)	10	None	1024	Return 1024 as final answer

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

Variable Tracker

Variable	Start	After Step 5	After Step 9	After Step 12	After Step 15	After Step 18
exp	10	0	1	2	5	10
half	undefined	undefined	1	2	4	32
result	undefined	1	2	4	32	1024

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 it. See steps 7-8 and 13-14 in execution_table.

Why does the recursion stop at exponent 0?

Exponent 0 means any number to power 0 is 1, the base case. This stops recursion and starts returning results. See step 5 in execution_table.

How does halving exponent reduce time complexity?

Each recursive call halves exponent, so calls are about log2(exp). This is why steps go from 10 to 5 to 2 to 1 to 0 quickly.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result computed at step 14?

A 64

B 16

C 32

D 8

💡 Hint

Check the 'Result Computed' column at step 14 in execution_table.

At which step does the exponent first become 0?

A Step 5

B Step 6

C Step 4

D Step 1

💡 Hint

Look at the 'Exponent' column in execution_table to find when it is 0.

If the exponent was 9 instead of 10, how would the final multiplication step change?

A No multiplication by base at the end

B Multiply by base once more at the end

C Multiply by base twice at the end

D Multiply by base before recursion

💡 Hint

Odd exponents cause multiplication by base after squaring, see steps 13-14.

Concept Snapshot

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

Full Transcript

Fast exponentiation calculates base raised to an exponent quickly by halving the exponent each step. The function calls itself with half the exponent, squares the result, and multiplies by base if the exponent is odd. The recursion stops when exponent is zero, returning 1. This reduces the number of multiplications from linear to logarithmic in the exponent size.

Practice

1. What is the main advantage of using fast exponentiation (power) algorithm over the simple repeated multiplication method?

easy

A. It works only for positive exponents

B. It reduces the time complexity from O(n) to O(log n)

C. It uses less memory by storing intermediate results

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand simple exponentiation time

   Simple repeated multiplication takes n multiplications for power n, so O(n) time.

2. Step 2: Analyze fast exponentiation time

   Fast exponentiation splits power by half each step, reducing steps to about log n, so O(log n) time.

3. Final Answer:

   It reduces the time complexity from O(n) to O(log n) -> Option B

4. Quick Check:

   Fast exponentiation = O(log n) [OK]

Hint: Fast exponentiation halves power each step [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Confusing time complexity with memory usage
• Assuming it only works for positive exponents

2. Which of the following is the correct base case for a recursive fast exponentiation function computing x^n?

easy

A. if (x == 0) return 0;

B. if (x == 1) return n;

C. if (n == 1) return 0;

D. if (n == 0) return 1;

Solution

1. Step 1: Identify base case for exponent zero

   Any number to the power 0 is 1, so if n == 0, return 1.

2. Step 2: Check other options

   Other options do not correctly represent the base case for power calculation.

3. Final Answer:

   if (n == 0) return 1; -> Option D

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Power zero always returns 1 [OK]

Common Mistakes:

• Returning 0 for n=1
• Confusing base case with input x values
• Returning n instead of 1 for base case

3. What is the output of the following C++ code snippet?

int fastPow(int x, int n) {
    if (n == 0) return 1;
    int half = fastPow(x, n / 2);
    if (n % 2 == 0) return half * half;
    else return half * half * x;
}

int main() {
    std::cout << fastPow(2, 5);
    return 0;
}

medium

A. 32

B. 16

C. 25

D. 10

Solution

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

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

2. Step 2: Calculate values bottom-up

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

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember odd powers multiply extra x once [OK]

Common Mistakes:

• Calculating 2^5 as 16 by missing odd case
• Confusing multiplication order
• Forgetting base case returns 1

4. The following code attempts to implement fast exponentiation but has a bug. What is the bug?

int fastPow(int x, int n) {
    if (n == 0) return 1;
    int half = fastPow(x, n / 2);
    if (n % 2 == 0) return half * half;
    else return half * half * n;
}

medium

A. Multiplying by n instead of x in the odd case

B. Missing base case for n == 1

C. Using integer division incorrectly

D. Not handling negative powers

Solution

1. Step 1: Check odd power multiplication

   In the odd case, code multiplies by n instead of x, which is incorrect.

2. Step 2: Confirm correct multiplication

   It should multiply by x to account for the extra factor in odd powers.

3. Final Answer:

   Multiplying by n instead of x in the odd case -> Option A

4. Quick Check:

   Odd power multiply by x, not n [OK]

Hint: Multiply by base x, not exponent n, for odd powers [OK]

Common Mistakes:

• Confusing n and x in multiplication
• Thinking base case missing causes this bug
• Ignoring negative power handling

5. You want to compute (3^13) % 7 efficiently using fast exponentiation with modulo. Which of the following code snippets correctly implements this?

hard

A. int modPow(int x, int n, int m) {
if (n == 0) return 1;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 0) return (halfSq * x) % m;
else return halfSq;
}

B. int modPow(int x, int n, int m) {
if (n == 0) return 0;
int half = modPow(x, n / 2, m);
int halfSq = (half + half) % m;
if (n % 2 == 0) return halfSq;
else return (halfSq * x) % m;
}

C. int modPow(int x, int n, int m) {
if (n == 0) return 1;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 1) return (halfSq * x) % m;
else return halfSq;
}

D. int modPow(int x, int n, int m) {
if (n == 1) return x % m;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 1) return halfSq;
else return (halfSq * x) % m;
}

Solution

1. Step 1: Check base case and modulo usage

   Base case returns 1 for n=0, correct. Multiplications use modulo to avoid overflow.

2. Step 2: Verify odd and even power handling

   For odd n, multiply halfSq by x modulo m; for even n, return halfSq. int modPow(int x, int n, int m) { if (n == 0) return 1; int half = modPow(x, n / 2, m); int halfSq = (half * half) % m; if (n % 2 == 1) return (halfSq * x) % m; else return halfSq; } matches this logic correctly.

3. Final Answer:

   code correctly implements fast exponentiation with modulo -> Option C

4. Quick Check:

   Modulo applied after each multiplication [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Returning 0 for base case
• Using addition instead of multiplication
• Swapping odd and even cases