In the following C function, let n ≥ m. int gcd(n,m) { if (n%m ==0) return m;…

Concept: when a recursive algorithm's working value shrinks by at least a constant multiplicative factor within every fixed-size block of calls, the recursion depth -- the number of calls before the base case -- grows in proportion to the logarithm of the starting value. This 'geometric shrinkage leads to logarithmic depth' principle is what governs binary search, repeated-squaring exponentiation, and the Euclidean GCD algorithm alike.

Application: this function replaces n by the remainder n % m on every call. Splitting on how large m is relative to n shows the value shrinks fast enough to fit that principle:

• If m ≤ n/2: the remainder n % m is already less than m, so it is less than n/2 -- the value more than halves in this single call.

• If m > n/2: the remainder is n − m (one subtraction of m from n), and since m > n/2, this remainder is less than n/2 -- so the value drops below n/2 within this call.

Either way, the working value is guaranteed to fall below half its previous value within at most two recursive calls. This means the value cannot be halved more than roughly log₂ n times before it collapses to the base case, and since each halving costs at most two recursive calls, the total number of recursive calls is bounded above by a constant multiple of log n (about 2·log₂ n) -- i.e. O(log n). Lamé's theorem shows this bound is also tight: when n and m are consecutive Fibonacci numbers, the recursion takes the maximum possible number of calls for that size of input, and that maximum itself grows as Θ(log n) (since Fibonacci numbers grow exponentially in their index). Combining the upper bound with this tight worst case gives Θ(log n).

Cross-check: the halving argument above is what actually establishes the Θ(log n) bound; tracing the worst-case pattern (consecutive Fibonacci numbers) at two sizes is only an illustrative sanity check on that argument, not a substitute for it -- a finite comparison of raw call counts can't by itself rule out another asymptotic class, since every class permits its own constants.

1. n = 13, m = 8: gcd(13,8) → gcd(8,5) → gcd(5,3) → gcd(3,2) → gcd(2,1) → base case (2 % 1 = 0). That is 4 recursive calls after the initial invocation (5 invocations in total).

2. n = 34, m = 21 (the next consecutive Fibonacci pair): gcd(34,21) → gcd(21,13) → gcd(13,8) → gcd(8,5) → gcd(5,3) → gcd(3,2) → gcd(2,1) → base case. That is 6 recursive calls after the initial invocation (7 invocations in total).

Going from n ≈ 13 to n ≈ 34 (roughly 2.6× larger) added a small, roughly constant number of extra recursive calls (2 more) rather than a count that visibly tracks n or √n directly -- exactly the pattern the halving argument predicts for Θ(log n), and consistent with it. The halving argument itself -- not this one small trace -- is what rules the other three options out rigorously.