如何求解递推式T(n)=T(6n/5)+1？无法应用主定理求指导

Hey there! I totally get why the Master Theorem feels useless here—since it’s designed for cases where subproblem sizes get smaller (i.e., ( b > 1 ) in the standard T(n) = aT(n/b) + f(n) form), and here you’ve got ( b = 5/6 < 1 ), which flips the script by making subproblems larger than the original. Let’s break down how to tackle this step by step:

First, Use Iterative Expansion (Unrolling the Recurrence) #

This is the go-to for non-standard recurrences where Master Theorem doesn’t apply. Let’s start by expanding the first few terms to spot a pattern:

• T(n) = T(6n/5) + 1
• Substitute the next level: T(6n/5) = T((6/5)^2 n) + 1, so now T(n) = T((6/5)^2 n) + 2
• After k expansions, this generalizes to:
  T(n) = T((6/5)^k n) + k

Now, Handle the Termination Condition #

Wait a second—if we keep expanding, (6/5)^k n keeps getting bigger and bigger, which would mean an infinite loop unless we have a concrete upper bound on the input size (like T(N) = O(1) when n ≥ N for some constant N). Let’s assume that’s the case: we need (6/5)^k n ≥ N to hit our base case.

Solve for k:

1. Start with (6/5)^k ≥ N/n
2. Take the logarithm of both sides (base 6/5):
   k ≥ log_{6/5}(N/n) = ln(N/n)/ln(6/5)
3. For asymptotic analysis, the constants and sign don’t matter—this simplifies to k = Θ(log n)

Substituting back into our expanded recurrence, we get T(n) = O(1) + Θ(log n) = Θ(log n).

Quick Sanity Check: Did You Flip the Subproblem Size? #

Most recurrence relations deal with smaller subproblems, so if you meant T(n) = T(5n/6) + 1 (subproblem size is 5/6 of n), the approach is almost identical. The termination condition would be when (5/6)^k n ≤ n₀ (our base case constant), and solving for k still gives T(n) = Θ(log n).

Either way, iterative expansion is the key here—you just need to track how many steps it takes to reach your base case, then count the number of constant terms added up.

内容的提问来源于stack exchange，提问作者Kioko Key