Should these conditions be satisfied?

[evinda]

Hello! (Wave)

I have to solve the recurrence relation

$$T(n)=\left\{\begin{matrix}
3T\left (\frac{n}{4} \right)+n & , n>1\\
1 &, n=1
\end{matrix}\right.$$

and prove by induction that the solution I found is right.

I found that the solution of the recurrence relation is $T(n)=O(n)$.

I started proving it like that:

• $n=1: T(1)=1 \leq c \cdot 1 \checkmark \text{ for } c \geq 1$
  
• We suppose that for any $m$, $2 \leq m <n , n>2$: $T(m) \leq c \cdot m$.
  
• We want to show that the claim stands for $n$.

But, then I noticed that we do not have a formula for $T \left ( \frac{n}{4} \right)$ when $n<4$ and also when $n \neq 4^k$.

So, do we have to suppose that $n \geq 4$ and $n=4^k$ ? (Thinking)

If so, at which point of the proof, do I have to claim it? (Thinking)

 

[evinda]

Could we prove that $T(n)=O(n)$ like that?

The recursive relation $T(n)=3T \left (\frac{n}{4} \right )+n$ is only defined for $n=4^k,k \geq 0$ , so:

$$T(n)=3T \left ( \frac{n}{4} \right )+n \Rightarrow T(4^k)=3T(4^{k−1})+4^k$$

• $ \displaystyle{ k=0 \Rightarrow n=1: T(1)=1 \leq c \cdot 1 \text{ if } c \geq 1 }$
  $$$$
• We suppose that $T(4^{k−1}) \leq c \cdot 4^{k−1}$
  $$$$
• $\displaystyle{ T(4^k)=3T(4^{k−1})+4^k \leq c \cdot 4^k \text{ if } c \geq 4 }$

So, $T(n)=O(n)$.

(Thinking) (Thinking)

 

[evinda]

Or do I have to prove by induction that $T(n)=4n-3 n^{ \log_4 3 }$ and not that $T(n)=O(n)$ ? (Thinking)

 

[chisigma]

For the truth something in the setting of this problem is not clear, in the first place the fact that we speak of the recurrence relation, which suggests that T (n) is a discrete function. In this case, however, if n is not multiple of 4, the function is not defined. For this reason, we assume that T (x) is an ordinary function of the continuous variable x in which case we should speak of functional relation ...

$\displaystyle T(x) = 3\ T(\frac{x}{4}) + x\ (1)$

Solving (1) is relatively comfortable if we suppose that T(x) is written in the form $\displaystyle T(x) = \sum_{n=0}^{\infty} a_{n}\ x^{n}$ and imposing the (1) You easily find that $a_{1}=4$ and $a_{n}=0$ for $n \ne 1$, so that the solution is $T(x) = 4\ x$. This This result, easily verifiable, however contrasts with the constraint T(1)=1 so that I must confess I did not understand the problem well ...

Kind regards

$\chi$ $\sigma$

P.S. It is useful to note, however, that for the solution found is $\displaystyle T(x) = \mathcal {O} (x)$...

 

[chisigma]

One possibility to put everything in place would be to write ...

$\displaystyle T(n) = 3\ T(\lfloor \frac{n}{4} \rfloor) + n,\ T(1)=1\ (1)$

Using the result I have obtained in the previous post it is easy to demonstrate that $\displaystyle T(n) \le 4\ n$ so that is $\displaystyle T(n) = \mathcal {O} (n)$... but is it really true? ...

Kind regards

$\chi$ $\sigma$