# 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. Aug 3, 2019 at 7:19
{"ft_lang_label":"__label__en","ft_lang_prob":0.7729581,"math_prob":1.0000097,"size":1113,"snap":"2023-14-2023-23","text_gpt3_token_len":468,"char_repetition_ratio":0.13345356,"word_repetition_ratio":0.0,"special_character_ratio":0.42767295,"punctuation_ratio":0.07003891,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000098,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-05-29T06:03:13Z\",\"WARC-Record-ID\":\"<urn:uuid:23351f7f-4916-4e90-8e9d-023f8c8dd6b7>\",\"Content-Length\":\"163001\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0d25395c-8fbb-4cc2-92ea-113f550f61aa>\",\"WARC-Concurrent-To\":\"<urn:uuid:f2b3b44c-e56d-4721-b52e-fc3b503bace9>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/112299/complexity-guess-and-induction-proof\",\"WARC-Payload-Digest\":\"sha1:I5NKAXGJRSGNMJ553CFM55H7XZ2WH2NI\",\"WARC-Block-Digest\":\"sha1:OGP4RV37IDKD4P6T457UQSB3MOX5ZG5F\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224644683.18_warc_CC-MAIN-20230529042138-20230529072138-00747.warc.gz\"}"}