# Solving T(n,m) = 3n + T(n/3,m/3)

I have the below recurrence: \begin{align} T(n, 1) &= 3n \\ T(1, m) &= 3m \\ T(n, m) &= 3n + T(\tfrac{n}{3}, \tfrac{m}{3}) \end{align}

How to get a tight asymptotic bound for $$T(n, n^2)$$ assuming that $$n$$ is a power of 3?

Using the substitution method for $$T(m,n)$$, I get a very weird relation:

$$T(n,m) = 3n + \frac{m}{3^{k-1}} + n\left(3 - \frac{1}{3^{k-1}}\right),$$ where $$k = \log_3 n$$.

• Welcome to the site! What's $k$? Sep 21, 2021 at 19:46
• Your solution cannot be right. Plugging $m=1$, you don't get $3n$.
Let $$S(N,M) = T(3^N,3^M)/3$$. If $$N \geq M$$ then \begin{align} S(N,M) &= 3^N + S(N-1,M-1) \\ &= 3^N + 3^{N-1} + S(N-2,M-2) + \\ &= \cdots \\ &= 3^N + \cdots + 3^{N-M+2} + S(N-M+1,1) \\ &= 3^N + \cdots + 3^{N-M+1}. \end{align} Similarly, if $$N \leq M$$ then \begin{align} S(N,M) &= 3^N + S(N-1,M-1) \\ &= 3^N + 3^{N-1} + S(N-2,M-2) + \\ &= \cdots \\ &= 3^N + \cdots + 3^{N-M+2} + S(1,M-N+1) \\ &= 3^N + \cdots + 3^{N-M+2} + 3^{M-N+1}. \end{align} It follows that $$S(N,M)= \Theta(3^N + 3^{M-N}),$$ and so $$T(n,m) = \Theta(n + m/n).$$ In particular, $$T(n,n^2) = \Theta(n).$$
• Indeed, $O(f + g)$ is the same as $O(\max(f,g))$. Sep 22, 2021 at 10:33