求解MysteryAlg递归算法的时间复杂度

Hey there! Let's walk through the time complexity of this MysteryAlg together—first, here's the code you shared for reference:

procedure MysteryAlg(x , n) 
    if n = 0 then
        return 1 
    end if
    if n = 1 then
        return x 
    end if
    if n is even then
        return MysteryAlg(x * x, n/2) 
    else
        return MysteryAlg(x * x, n/2) * x 
    end if
end procedure

First off, this is the exponentiation by squaring algorithm, a super efficient way to calculate (x^n)! Now let's dig into its time complexity:

• Recursive Problem Reduction: Every recursive call cuts the problem size in half:

  • If (n) is even: We call MysteryAlg with (x*x) and (n/2)—so we're dealing with a problem that's half the original size.
  • If (n) is odd: Same reduction to (n/2) (using integer division, like 7 becomes 3), then we just multiply the result by (x) (a constant-time operation).
  • The base cases ((n=0) or (n=1)) just return a value immediately—no extra work, so that's (O(1)) time.

• How Many Recursive Steps?: Since we're halving (n) every time, the number of steps we need to reach a base case is equal to the number of times you can divide (n) by 2 until you hit 1. That's (\log_2 n) steps, which we simplify to (O(\log n)) (the base doesn't matter for big-O notation).

• Constant Work per Step: Each step (excluding the recursive sub-call) only involves simple checks (is (n) 0/1? Is it even?) and arithmetic operations—all of these take constant (O(1)) time.

Adding it all up, the total time complexity of MysteryAlg is (O(\log n)). This is way better than the naive approach of multiplying (x) (n) times (which is (O(n)))—especially when (n) is really large, this logarithmic time difference is huge.

内容的提问来源于stack exchange，提问作者Umama Khalid