1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.