Complexity guess and induction proof

Question

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?

Answer 1

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.

Answer 2

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