Fast Exponentiation Power in Log N in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Fast Exponentiation (Power) algorithm?

It reduces the number of multiplications by repeatedly squaring the base and using the binary representation of the exponent, achieving O(log n) time instead of O(n).

beginner

In Fast Exponentiation, what do you do when the current exponent bit is 1?

Multiply the result by the current base value before squaring the base for the next bit.

intermediate

Why does Fast Exponentiation run in O(log n) time?

Because it halves the exponent at each step by shifting bits, so the number of steps equals the number of bits in the exponent, which is about log2(n).

intermediate

Show the step-by-step calculation of 3^13 using Fast Exponentiation.

13 in binary is 1101. Steps: result=1, base=3 Bit 1 (LSB): multiply result by base → result=3 Square base → base=9 Bit 0: no multiply Square base → base=81 Bit 1: multiply result by base → result=3*81=243 Square base → base=6561 Bit 1: multiply result by base → result=243*6561=1594323 Final result=1594323

beginner

What is the base case for the Fast Exponentiation recursive approach?

When the exponent is 0, return 1 because any number to the power 0 is 1.

What is the time complexity of Fast Exponentiation for calculating x^n?

A O(1)

B O(n)

C O(n log n)

D O(log n)

Fast Exponentiation reduces the exponent by half each step, so it runs in O(log n) time.

In Fast Exponentiation, if the current exponent bit is 0, what should you do?

A Add base to result

B Multiply result by base

C Square the base only

D Stop the algorithm

When the bit is 0, you only square the base and do not multiply the result.

Which of these is NOT a benefit of Fast Exponentiation?

A Always uses recursion

B Uses less memory than naive method

C Works well with modular arithmetic

D Faster calculation for large exponents

Fast Exponentiation can be implemented iteratively or recursively; recursion is not mandatory.

What is the result of 2^5 using Fast Exponentiation?

A 32

B 10

C 25

D 64

2^5 = 32.

Which operation is repeated in Fast Exponentiation to reduce the exponent?

A Adding 1

B Dividing exponent by 2

C Multiplying exponent by 2

D Subtracting 1

The exponent is divided by 2 (shifted right) each step to reduce the problem size.

Explain how Fast Exponentiation reduces the number of multiplications compared to the naive method.

Think about how the exponent is broken down in powers of two.

Describe the iterative steps to compute 5^11 using Fast Exponentiation.

Walk through each bit of the exponent from least significant to most.