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↓

Is exponent even?

Yes→Square base, halve exponent

↓

Recursive call with new base and exponent

↓

Multiply result by base

↓

Return result

This flow shows how the exponent is reduced by half each step if even, or multiplied by base if odd, until exponent reaches zero.

Execution Sample

DSA C

int fastPower(int base, int exp) {
    if (exp == 0) return 1;
    int half = fastPower(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    else return half * half * base;
}

Computes base raised to exp using recursion and halving exponent for efficiency.

Execution Table

Step	Operation	Exponent	Recursive Call Result	Calculation	Return Value
1	Call fastPower(2, 10)	10	-	-	-
2	Call fastPower(2, 5)	5	-	-	-
3	Call fastPower(2, 2)	2	-	-	-
4	Call fastPower(2, 1)	1	-	-	-
5	Call fastPower(2, 0)	0	-	Base case reached	1
6	Return from fastPower(2, 0)	0	1	-	1
7	Calculate half * half * base for exp=1 (odd)	1	1	1 * 1 * 2	2
8	Return from fastPower(2, 1)	1	2	-	2
9	Calculate half * half for exp=2 (even)	2	2	2 * 2	4
10	Return from fastPower(2, 2)	2	4	-	4
11	Calculate half * half * base for exp=5 (odd)	5	4	4 * 4 * 2	32
12	Return from fastPower(2, 5)	5	32	-	32
13	Calculate half * half for exp=10 (even)	10	32	32 * 32	1024
14	Return from fastPower(2, 10)	10	1024	-	1024

💡 Recursion ends when exponent reaches 0, returning 1 as base case.

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
exp	10	0	1	2	5	10	10
half	-	1	1	2	4	32	32
return_value	-	1	2	4	32	1024	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, so we multiply once more by base to compensate, as shown in steps 7 and 11.

Why does the recursion stop at exponent 0?

Exponent 0 means base^0 which is 1, the base case in step 5 stops recursion and returns 1.

How does halving the exponent reduce time complexity?

Each recursive call halves the exponent (steps 2,3,4), so the number of calls is proportional to log2(exponent), making it much faster than multiplying base exponent times.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the calculation performed?

A 4 * 4 * 2

B 2 * 2

C 1 * 1 * 2

D 32 * 32

💡 Hint

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

At which step does the exponent become zero, ending recursion?

A Step 3

B Step 5

C Step 9

D Step 14

💡 Hint

Look for the base case with exponent 0 in execution_table.

If the exponent was 8 instead of 10, how would the number of recursive calls change?

A Fewer calls than for 10

B Same number of calls as for 10

C More calls than for 10

D No recursive calls

💡 Hint

Check variable_tracker for how exponent halves each step.

Concept Snapshot

Fast Exponentiation computes base^exp in O(log n) time.
Use recursion: if exp==0 return 1.
Else compute half = fastPower(base, exp/2).
If exp even: return half*half.
If exp odd: return half*half*base.
Reduces multiplications by halving exponent each step.

Full Transcript

Fast Exponentiation calculates power by reducing the exponent quickly. It uses recursion to halve the exponent each time. When exponent is zero, it returns 1. For even exponents, it squares the half result. For odd exponents, it multiplies the squared half result by the base once more. This method runs in logarithmic time, much faster than multiplying base repeatedly. The execution table shows each recursive call and calculation step, with the variable tracker following exponent and intermediate results. Key moments clarify why multiplication by base happens only for odd exponents and why recursion stops at zero exponent.