Fast Exponentiation Power in Log N in DSA Rust - Time & Space Complexity

Time Complexity: Fast Exponentiation Power in Log N

O(log n)

Understanding Time Complexity

We want to understand how fast the power calculation grows as the exponent gets bigger.

How does the number of steps change when we raise a number to a large power?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn fast_power(base: i64, exponent: i64) -> i64 {
    if exponent == 0 {
        return 1;
    }
    let half = fast_power(base, exponent / 2);
    if exponent % 2 == 0 {
        half * half
    } else {
        half * half * base
    }
}
    

This code calculates the power of a number using a method that splits the problem in half each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls that halve the exponent each time.
• How many times: About log base 2 of the exponent times.

How Execution Grows With Input

Each step cuts the exponent roughly in half, so the number of steps grows slowly as the exponent grows.

Input Size (exponent)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the exponent adds only one more step.

Final Time Complexity

Time Complexity: O(log n)

This means the steps needed grow very slowly compared to the size of the exponent.

Common Mistake

[X] Wrong: "The function runs in linear time because it looks like it calls itself many times."

[OK] Correct: Each call reduces the problem size by half, so the total calls grow logarithmically, not linearly.

Interview Connect

Knowing how to quickly calculate powers is a useful skill that shows you understand efficient problem solving.

Self-Check

"What if we changed the code to multiply the base exponent times without halving? How would the time complexity change?"

Practice

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

easy

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

B. It uses less memory than repeated multiplication

C. It works only for positive exponents

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand repeated multiplication time

   Repeated multiplication multiplies the base n times, so it takes O(n) time.

2. Step 2: Understand fast exponentiation time

   Fast exponentiation uses squaring and halves the exponent each step, so it takes O(log n) time.

3. Final Answer:

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

4. Quick Check:

   Fast exponentiation = O(log n) [OK]

Hint: Fast exponentiation halves exponent each step [OK]

Common Mistakes:

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

2. Which of the following Rust function signatures correctly represents a fast exponentiation function for integers?

easy

A. fn fast_pow(base: i32, exp: i32) -> i32

B. fn fast_pow(base: i32, exp: i32) -> ()

C. fn fast_pow(base: i32) -> i32

D. fn fast_pow(exp: i32, base: i32) -> i32

Solution

1. Step 1: Check parameters needed

   Fast exponentiation needs base and exponent as inputs, both integers.

2. Step 2: Check return type

   It returns the computed power as an integer, so return type is i32.

3. Final Answer:

   fn fast_pow(base: i32, exp: i32) -> i32 -> Option A

4. Quick Check:

   Correct signature includes base, exp, returns i32 [OK]

Hint: Function needs base, exponent, returns result [OK]

Common Mistakes:

• Missing exponent parameter
• Wrong return type (void)
• Swapping parameter order incorrectly

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

fn fast_pow(mut base: i32, mut exp: i32) -> i32 {
    let mut result = 1;
    while exp > 0 {
        if exp % 2 == 1 {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    result
}

fn main() {
    println!("{}", fast_pow(3, 5));
}

medium

A. 125

B. 243

C. 15

D. 81

Solution

1. Step 1: Understand fast_pow(3, 5)

   3^5 = 3*3*3*3*3 = 243.

2. Step 2: Trace the code logic

   Loop squares base and halves exp, multiplying result when exp is odd, correctly computing 243.

3. Final Answer:

   243 -> Option B

4. Quick Check:

   3^5 = 243 [OK]

Hint: Calculate 3^5 = 243 quickly [OK]

Common Mistakes:

• Calculating 5^3 instead of 3^5
• Confusing multiplication steps
• Forgetting to multiply result when exp is odd

4. Identify the bug in this Rust fast exponentiation function:

fn fast_pow(base: i32, mut exp: i32) -> i32 {
    let mut result = 1;
    let mut base = base;
    while exp > 0 {
        if exp % 2 == 0 {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    result
}

medium

A. The result should start at 0, not 1

B. The base should not be mutable

C. The loop should run while exp >= 0

D. The condition should check if exp % 2 == 1, not 0

Solution

1. Step 1: Check condition for multiplying result

   Multiplying result should happen when exp is odd (exp % 2 == 1), not even.

2. Step 2: Confirm other parts

   Mutable base is correct, result starts at 1, loop condition is correct.

3. Final Answer:

   The condition should check if exp % 2 == 1, not 0 -> Option D

4. Quick Check:

   Multiply result only when exp is odd [OK]

Hint: Multiply result only if exponent is odd [OK]

Common Mistakes:

• Multiplying when exponent is even
• Starting result at 0
• Loop running one extra time

5. You want to compute (2^30) % 1000 efficiently using fast exponentiation in Rust. Which modification is necessary to the standard fast exponentiation algorithm to handle this correctly?

hard

A. Increase the base to 1000 before starting

B. Use floating point numbers instead of integers

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

D. Multiply result only when exponent is even

Solution

1. Step 1: Understand modulo exponentiation

   To compute (base^exp) % mod efficiently, apply modulo after each multiplication to avoid overflow.

2. Step 2: Modify fast exponentiation

   Insert modulo operation after multiplying result and squaring base to keep values within range.

3. Final Answer:

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

4. Quick Check:

   Modulo after each step prevents overflow [OK]

Hint: Apply modulo after every multiplication [OK]

Common Mistakes:

• Using floats causing precision errors
• Not applying modulo each step causing overflow
• Incorrectly multiplying on even exponent