Fast Exponentiation Power in Log N in DSA Python - 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 a time complexity of O(log n).

intermediate

How does Fast Exponentiation handle odd exponents differently than even exponents?

For odd exponents, it multiplies the result by the base once and then reduces the exponent by 1 to make it even, allowing repeated squaring to continue.

beginner

What is the time complexity of Fast Exponentiation compared to the naive method?

Fast Exponentiation runs in O(log n) time, which is much faster than the naive O(n) method that multiplies the base n times.

intermediate

Show the binary representation of exponent 13 and explain how it helps in Fast Exponentiation.

13 in binary is 1101. Fast Exponentiation uses this to multiply powers of base corresponding to bits set to 1 (2^3, 2^2, 2^0), skipping unnecessary multiplications.

beginner

Write the base case for the recursive Fast Exponentiation algorithm.

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

What is the time complexity of Fast Exponentiation?

A O(log n)

B O(n)

C O(n log n)

D O(1)

Fast Exponentiation reduces the number of multiplications by using repeated squaring, resulting in O(log n) time.

In Fast Exponentiation, what do you do when the exponent is odd?

A Multiply result by base and subtract 1 from exponent

B Divide exponent by 2

C Return 0

D Multiply base by itself twice

For odd exponents, multiply the result by base once and reduce exponent by 1 to make it even.

Which of these is NOT a benefit of Fast Exponentiation?

A Faster computation for large exponents

B Reduces time complexity from O(n) to O(log n)

C Uses binary representation of exponent

D Always uses more multiplications than naive method

Fast Exponentiation uses fewer multiplications than the naive method, not more.

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

A 0

B 1

C 2

D Undefined

Any number raised to the power 0 is 1.

Which binary bit positions are used in Fast Exponentiation for exponent 13 (binary 1101)?

A Positions 0 and 1

B Positions 1 and 2

C Positions 0, 2, and 3

D Positions 1, 2, and 3

Bits set to 1 are at positions 0, 2, and 3 in binary 1101 (right to left, zero-based).

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

Think about how powers of two help skip many multiplications.

Describe the steps to compute 3^13 using Fast Exponentiation.

Use the binary bits to decide when to multiply.