0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Jeff Erickson has good notes on this. Might want to look at it. This is called domain transformation. jeffe.cs.illinois.edu/teaching/algorithms/notes/… $\endgroup$ Jul 6, 2022 at 5:05
  • 1
    $\begingroup$ When $n$ is not divisible by $3$, $\frac n3$ could be interpreted as the quotient by default. But in real-life situations, it is more likely that the recurrence follows from the data set being processed in three parts of the closest possible sizes and the real recurrence would rather involve $2T(\lfloor\frac n3\rfloor)+T(n-2\lfloor\frac n3\rfloor)$. $\endgroup$
    – user16034
    Aug 5, 2022 at 14:20

2 Answers 2

0
$\begingroup$

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))$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.