Time Complexity of the Given C++ gcd Function

Time Complexity of the Given C++ `gcd` Function

Verified Sources

Sep 12, 2026

The provided C++ function is an iterative form of the Euclidean algorithm that repeatedly replaces $(n,m)$ with $(m, n \bmod m)$ until $m=0$ , returning the final $n$ .

Algorithmically, this is the same core recurrence as the Euclidean algorithm:

(n,m) \rightarrow (m,\, n \bmod m),

and the loop continues while $m>0$ . In the worst case (e.g., when inputs are consecutive Fibonacci numbers), the number of iterations grows on the order of $\Theta(\log n)$ (more precisely $\Theta(\log \min(n,m))$ ), so for $n>m$ it is $\Theta(\log n)$ .

Therefore, the correct option is (i) $\Theta(\log n)$ .

Key learning terms:

Euclidean algorithm
Modulus operation
Loop iteration
Worst-case complexity

Note: The complexity discussed below counts loop iterations; each iteration performs a constant amount of arithmetic and swaps.

Euclidean GCD Algorithm - Easy Explanation and Implementation

Why the loop runs $\Theta(\log n)$ times (for $n>m$ )

Let $n>m>0$ . Each iteration replaces $(n,m)$ with $(m, n \bmod m)$ , where

0 \le n \bmod m < m. $$] So the second value strictly decreases, and the algorithm terminates when $m$ becomes $0$. A key worst-case insight is that the Euclidean algorithm decreases the numbers “slowly” when quotients of the division are as small as possible, which happens for inputs that follow a Fibonacci-like structure. In that worst case, the number of remainder steps grows proportionally to the index of the Fibonacci number, which is logarithmic in the magnitude of the input. Thus for $n>m$, the worst-case number of iterations is

\Theta(\log n),

and the total runtime is also $\Theta(\log n)$ because each iteration costs $O(1)$.

Time-complexity reasoning for the Euclidean-style gcd loop

1
Step 1
Inside the loop, the code does $n=n\%m$ and then swaps, implementing the transformation $(n,m)\leftarrow (m, n\bmod m)$ .
2
Step 2
After computing $n\%m$ , the new remainder satisfies $0 \le (n\bmod m) < m$ , so the next loop's $m$ is smaller than the previous $m$ .
3
Step 3
The largest number of iterations occurs when the remainder decreases as slowly as possible, which is known to correspond to a Fibonacci/worst-case Euclid pattern.
4
Step 4
Because each loop iteration does constant work (one modulus, one swap, comparisons), runtime is proportional to the number of iterations.
5
Step 5
For $n>m$ , the iteration count is $\Theta(\log n)$ , hence total time complexity is $\Theta(\log n)$ .

Pro Tip

When analyzing Euclidean-style code, focus on how the pair $(n,m)$ transforms: if the second argument decreases in a pattern tied to Fibonacci numbers, the runtime becomes logarithmic.

Common pitfall

Don’t treat $n\%m$ as “reducing by a constant fraction every time.” Sometimes it reduces slowly; worst-case Euclid is still only logarithmic, but the proof requires the Euclid/Fibonacci argument.

Matching options to expected gcd runtime

Euclidean algorithm worst-case iteration count is logarithmic in input magnitude.

Exam-style clarification

Knowledge Check

Question 1 of 4

Q1Single choice

For the given gcd implementation (iterative Euclidean algorithm), assuming $n>m$ , what is the worst-case time complexity?

Θ(log n)

Ω(n)

Θ(log log n)

Θ(√n)

Explore Related Topics

Counting Relations on a Set with $n$ Elements

Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for $\{4,10,3,12,20,7\}$

The lesson shows how dynamic programming determines the cheapest way to multiply the matrix chain with dimensions  $\{4,10,3,12,20,7\}$ .

The recurrence $m[i,j]=\min_{i\le k<j}\big(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\big)$ with $m[i,i]=0$ computes optimal sub‑costs.
Filling the cost table yields $m[1,5]=1344$ , and the split table gives the top‑level split $k=2$ .
The optimal parenthesization is  $(A_1A_2)\big((A_3A_4)A_5\big)$ , requiring $120+720+420+84=1344$ scalar multiplications.
The bottom‑up algorithm runs in $O(n^3)$ time and uses $O(n^2)$ space.

Bipartite Testing When No Odd-Length Cycles Exist: Best Known Time Complexity

Browse all research articles

Time Complexity of the Given C++ gcd Function