MHB Should these conditions be satisfied?

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Conditions
AI Thread Summary
The recurrence relation T(n) = 3T(n/4) + n is examined, with the proposed solution being T(n) = O(n). The discussion highlights the challenge of proving this solution, particularly for values of n that are not powers of 4, leading to questions about the validity of the induction proof. It is suggested that T(n) may only be defined for n = 4^k, which complicates the proof process. The conversation ultimately questions whether T(n) should be expressed as O(n) or in a more specific form, revealing uncertainties about the problem's constraints and definitions.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
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) :confused: (Thinking)
 
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)
 
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)$...
 
Last edited:
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$
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top