How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$

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)$$?

• $T(n)=\Omega(n)$ definition usually means $n \to \infty$ type aproximation. What you understand under $n \in X$? Mar 4, 2021 at 2:50
• @zkutch Thank u for replying. I don't understand what you mean? Mar 4, 2021 at 3:07
• 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? Mar 4, 2021 at 3:25
• @zkutch what if we change the definition of Ω, the set is now (N,+∞) ∩ X Mar 4, 2021 at 7:21
• @zkutch: $T(n)=\Omega(n)$ is short for $\exists S(n):S(n)=\Omega(n)\land \forall n\in X:T(n)=S(n)$.
– user16034
Mar 24, 2023 at 12:53

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.

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

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$$.