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$

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.