Complexity guess and induction proof I was trying to prove by induction that
$$
T(n) =      \begin{cases}
       1 &amp;\quad\text{if } n\leq 1\\
       T\left(\lfloor\frac{n}{2}\rfloor\right) + n &amp;\quad\text{if } n\gt1 \\
     \end{cases}
$$
is $\Omega(n)$ implying that $\exists c&gt;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 &lt; 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?
You're overthinking. $T(\lfloor\frac{n}{2})\rfloor \ge 1 \Rightarrow T(n) = T(\lfloor\frac{n}{2})\rfloor + n &gt; n \Rightarrow T(n) = \Omega(n)$