0
$\begingroup$

Consider the following recurrence relationship.

\begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\ 2T\left(\displaystyle\frac{n-1}{2}\right), &n \ \mbox{is odd number}& \end{cases} \nonumber \\ T(1) &=& 1 \end{eqnarray}

How to prove there exists an infinite set $X$, that when $n∈X$, $T(n)=Ω(n)$?

$\endgroup$
9
  • 1
    $\begingroup$ $T(n)=\Omega(n)$ definition usually means $n \to \infty$ type aproximation. What you understand under $n \in X$? $\endgroup$
    – zkutch
    Mar 4, 2021 at 2:50
  • $\begingroup$ @zkutch Thank u for replying. I don't understand what you mean? $\endgroup$
    – t24akeru
    Mar 4, 2021 at 3:07
  • $\begingroup$ Definition for $T(n)=\Omega(n)$ is $\exists N,C$ such, that $T(n)\geqslant C \cdot n$ for $\forall n \gt N$. So set here is $(N, +\infty)\cap \mathbb{N}$. Now about which $n \in X$ are you asking? $\endgroup$
    – zkutch
    Mar 4, 2021 at 3:25
  • $\begingroup$ @zkutch what if we change the definition of Ω, the set is now (N,+∞) ∩ X $\endgroup$
    – t24akeru
    Mar 4, 2021 at 7:21
  • $\begingroup$ @zkutch: $T(n)=\Omega(n)$ is short for $\exists S(n):S(n)=\Omega(n)\land \forall n\in X:T(n)=S(n)$. $\endgroup$
    – user16034
    Mar 24, 2023 at 12:53

2 Answers 2

1
$\begingroup$

Here is the idea. When $n$ is even, $$ \frac{T(n)}{n} \approx \frac{1}{2} \frac{T(n/2)}{n/2}. $$ In contrast, when $n$ is odd, $$ \frac{T(n)}{n} \approx \frac{T(\lfloor n/2 \rfloor)}{\lfloor n/2 \rfloor}, $$ due to the factor 2 in the recurrence.

This suggests that in order to find your set $X$, you want to hit the "odd" case all the way. If $m = \frac{n-1}{2}$ then $n = 2m+1$, so if $m$ is a good choice, so is $n$. This suggests considering the sequence defined by $n_0 = 1$ and $n_{t+1} = 2n_t+1$, which is $1,3,7,15,\ldots$. As you can see, $n_t = 2^{t+1}-1$. The value of $T$ on this sequence is $1,2,4,8,\ldots$, that is, $T(n_t) = 2^t$.

We can now prove by induction that $T(2^{t+1}-1) = 2^t$. When $t = 0$, this just states the base case $T(1) = 1$. When $t > 0$, $$ T(2^{t+1}-1) = 2T\left(\frac{2^{t+1}-2}{2}\right) = 2T(2^t-1) = 2\cdot 2^{t-1} = 2^t. $$ Finally, note that $$ T(2^{t+1}-1) = 2^t \geq \frac{1}{2} (2^{t+1}-1), $$ and so you can take $X = \{ 2^{t+1}-1 : t \in \mathbb N \}$ as your infinite set.

$\endgroup$
2
  • $\begingroup$ Thank you for answering. I am still thinking why it is 𝑇(𝑛)=Ω(𝑛).Could you explain more if you can? $\endgroup$
    – t24akeru
    Mar 4, 2021 at 14:53
  • $\begingroup$ I suggest taking a deeper look at the definition. $\endgroup$ Mar 4, 2021 at 16:18
0
$\begingroup$

If all arguments of $T$ are even, i.e. when $n$ is a power of $2$, the solution of the recurrence is $T(n)=\log_2(n)+1$. (Because $\log_2(2^k)+1=\log_2(2^{k-1})+1+1$.)

On the opposite, when all arguments of $T$ are odd, the solution is $T(n)=\dfrac{n+1}2$ (Because $\dfrac{n+1}2=2\dfrac{\dfrac{n-1}2+1}2$.)


Resolution of the second recurrence:

For all odd arguments,

$$T(n)=2T\left(\frac{n-1}2\right)$$ becomes, with the ansatz $T(n)=an+b$,

$$an+b=2a\left(\left(\frac{n-1}2\right)+b\right),$$ giving $a=b$. Then the initial condition makes $a+b=1$.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .