How to prove that we can study the complexity of Recurrence Relations by always giving in input a power of how many children each node creates?

Question

Let's say we have the following Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ 3T(\frac{n}{3}) + \Theta(n) & \text{otherwise} \end{cases} $$ I've been taught I can study its complexity by giving into input a power of 3 to calculate its height and consequently its total cost.

I'd like a proof of why this can be done, despite the fact the tree can receive a number which is not power of three, thus making it taller or shorter than what initially studied. Thank you.

Answer 1

When does it work? This trick would work if $T(n)$ satisfies $$T(3 n) = \Theta(T(3n)) \qquad \qquad (Cond.)$$ which holds if it belongs to polynomial family, which is the case when $T(n)=O(a T(n/b)) +O(n)$ for constants $a,b=O(1),b>1$. Observe that for all numbers $n$ there is $k$ such that $3^k\le n< 3^{k+1}$ and we have $$3^k\le n< 3^{k+1}\implies T(3^k)\lesssim T(n)\lesssim T(3^{k+1})\lesssim T(3^{k+1}) \overset{(Cond.)}{ \implies } T(n)=\Theta(3^k) $$ where $f \lesssim g$ denotes $f=O(g)$.

When it doesn't work? Note that $(Cond.)$ can be violated, notably when $T(n)$ grows exponentially. If for constant $\alpha$ we have $$T(n)=\Theta(\alpha^{3n})\implies T(n)=o(T(3n))$$

Answer 2

Let us consider the recurrence

$$T(n)=3T\left(\left\lfloor\frac n3\right\rfloor\right)+n.$$

We can show that the function $T$ is strictly growing because by complete induction, if $T$ is increasing up to $3m$,

$$T(3m)=3T(m)+3m\\ <T(3m+1)=3T(m)+3m+1\\ <T(3m+2)=3T(m)+3m+2\\ <T(3m+3)=3T(m+1)+3m+3$$

so that $T$ is increasing up to $3m+3$.

Given that $T$ is growing, when $n$ is comprised between two powers of $3$, $T(n)$ is comprised between $T$ for these two powers. So the order of growth between powers is the same as on powers.