The running time of an algorithm is represented by the following recurrence…

Answer: Θ(n) — linear time.

Master Theorem analysis:

• Write the recurrence as T(n)=a·T(n/b)+f(n) with a=1, b=3, and f(n)=c n.

• Compute n^{log_b a} = n^{log_3 1} = n^0 = 1.

• Compare f(n)=Θ(n) to n^{log_b a}=1. f(n) = n^{0+1}, i.e. polynomially larger with ε=1, so this is Case 3 of the Master Theorem.

• Verify the regularity condition: a·f(n/b) = 1·c(n/3) = c n/3 ≤ k·f(n) for some k<1 (take k=1/2), so the condition holds.

• Therefore T(n)=Θ(f(n))=Θ(n).

Recurrence-tree intuition:

The work at levels of the recursion are: cn (root), c n/3 (next level), c n/9, ... This is a geometric series with ratio 1/3, so the total cost is cn · (1/(1-1/3)) = (3/2) c n = Θ(n).

Conclusion: The running time is Θ(n).