# Complexity guess and induction proof

I was trying to prove by induction that
$$T(n) = \begin{cases} 1 &\quad\text{if } n\leq 1\\ T\left(\lfloor\frac{n}{2}\rfloor\right) + n &\quad\text{if } n\gt1 \\ \end{cases}$$ is $$\Omega(n)$$ implying that $$\exists c>0, \exists m\geq 0\,\,|\,\,T(n) \geq cn \,\,\forall n\geq m$$

Base case : $$T(1) \geq c1 \implies c \leq 1$$

Now we shall assume that $$T(k) = \Omega(k) \implies T(k) \geq ck \,\,\forall k < n$$ and prove that $$T(n) = \Omega(n)$$.
$$T(n) = T(\lfloor{\frac{n}{2}}\rfloor) + n \geq c\lfloor{\frac{n}{2}}\rfloor + n \geq c \frac{n}{2} -1 + n \geq n\left(\frac{c}{2} - \frac{1}{n} + 1\right) \geq^{?} cn\\ c \leq 2 - \frac{2}{n}$$
So we have proved that $$T(n) \geq c n$$ in :

1) The base case for $$c \leq 1$$

2) The inductive step for $$c \leq 2 - \frac{2}{n}$$

Yet we have to find a value that satisfies them both for all $$n\geq 1$$, the book suggest such value is $$c = 1$$ which to me is not true since :

$$1 \leq 1\\1\leq2 - \frac{2}{n}\implies 1 \leq 0 \text{ for n = 1}$$
My guess would be $$0$$ but is not an acceptable value; So we just say its $$\Omega(n)$$ but for $$n \gt 1$$?Or how can we deal with it?

It looks like you have used a heavy machinery but only to arrive at a wrong conclusion.

Here is a simple proof that $$T(n)=\Omega(n)$$.

• It is clear that $$T(n)\ge0$$.
• Hence $$T(n)=T(\lfloor{\frac n2}\rfloor)+n\ge n$$ for $$n\ge2$$. Done.

Now we shall assume that $$T(k) = \Omega(k) \implies T(k) \geq ck \,\,\forall k < n$$ and prove that $$T(n) = \Omega(n)$$.

$$T(n) = T(\lfloor{\frac{n}{2}}\rfloor) + n \geq c\lfloor{\frac{n}{2}}\rfloor + n \geq c \frac{n}{2} -1 + n \geq n\left(\frac{c}{2} - \frac{1}{n} + 1\right) \geq^{?} cn\\ c \leq 2 - \frac{2}{n}$$

What you are doing above is trying to find a sufficient condition for a wanted $$c$$. In the end, you have found that "$$c \leq 2 - \frac{2}{n}$$ for all $$n$$" is a sufficient condition for a wanted $$c$$. However, that condition is not necessary for a wanted $$c$$.

Second, you could have succeeded had you noticed that you can assume $$n\ge2$$ in " $$T(k) \geq ck \,\,\forall k < n$$ and prove that $$T(n) = \Omega(n)$$". Then you would have found "$$c \leq 2 - \frac{2}{n}$$ for all $$n\ge2$$", which is equivalent to "$$c\le1$$". So you could have obtained $$c=1$$ at all.

Third, in order to prove $$T(n)=\Omega(n)$$, you do not have to show that for some $$c\gt0$$, $$T(n)\ge cn$$ for all $$n$$. It is enough to show that there exists $$m$$ and $$c\gt0$$ such that $$T(n)\ge cn$$ for all $$n\ge m$$. So you can try $$m=2$$ or $$m=2019$$ or $$m=10^{80}$$.

The following exercise is somewhat off the track of big $$\Omega$$-notation.

Exercise. Show that $$T(n)=2n-b(n)$$, where $$b(n)$$ is the number of 1s in the binary representation of $$n$$. Show that $$T(n)\sim 2n$$ when $$n$$ goes to infinity.

You're overthinking. $$T(\lfloor\frac{n}{2})\rfloor \ge 1 \Rightarrow T(n) = T(\lfloor\frac{n}{2})\rfloor + n > n \Rightarrow T(n) = \Omega(n)$$

• Sorry but I need to prove it by induction. – Luca Grignani Aug 3 at 7:19