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

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

This code calculates base raised to the exponent using repeated squaring.

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₂(exponent) times, because the exponent is divided by 2 each call.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(log n)

This means the steps grow slowly, only increasing by one each time the exponent doubles.

Common Mistake

[X] Wrong: "The function does one multiplication per exponent value, so it is O(n)."

[OK] Correct: The function splits the problem in half each time, so it does far fewer steps than the exponent itself.

Interview Connect

Understanding this method shows you can improve simple tasks by clever thinking, a skill valued in coding challenges and interviews.

Self-Check

"What if we changed the function to use a loop instead of recursion? 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 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