Do we have to find a specific value?

[evinda]

Hi! (Smile)

Given that $T(n)=2T\left( \frac{n}{2}\right)+n^3$, I want to show that $T(n)=\Theta(n^3)$.

In my notes, it is shown like that that: $T(n)=O(n^3) \Rightarrow T(n) \leq cn^3$:

$$T(n)=2T\left( \frac{n}{2} \right)+n^3 \leq 2c \left( \frac{n}{2} \right)^3+n^3=\frac{cn^3}{4}+n^3=n^3 \left( \frac{c}{4}+1\right ) \leq c n^3 \text{ when } c \geq \frac{4}{3}$$

So, for $c \geq \frac{4}{3}$ and $n \geq 0$, we have that $T(n)=O(n^3)$.
When we write it like that:

We suppose that $\forall k<n, \exists n_0 \in \mathbb{N}$, such that $\forall k \geq n_0$:
$$c_1 k^3 \leq T(k) \leq c_2 k^3 $$

We will show that $c_1 n^3 \leq T(n) \leq c_2 n^3$.

$$T(n)=2T\left( \frac{n}{2}\right)+n^3 \leq \dots \dots \leq c_2n^3, \text{ when } c_2 \geq \frac{n}{3}$$

do we have to find a $n_1$ for which the relation stands? (Thinking)

 

[Valkarie]

No, we don't have to find $n_1$ since we are only trying to show that $T(n)=\Theta(n^3)$. This means that we just need to show that there exists constants $c_1$ and $c_2$ such that $c_1 n^3 \leq T(n) \leq c_2 n^3$ holds for all $n \geq 0$. To prove this, we can use the fact that $T(n) \leq c_2n^3$ holds when $c_2 \geq \frac{n}{3}$. Therefore, for any $n \geq 0$, we have that $c_2 \geq \frac{n}{3}$ and thus $T(n) \leq c_2n^3$ holds. We can also use a similar argument to show that $c_1 n^3 \leq T(n)$ holds for all $n \geq 0$, which shows that $T(n)=\Theta(n^3)$.