New answers tagged

3

You do not have to prove things by induction. For example, you can prove $\forall n : \mathbb{N} \,.\, n = n$ without induction by applying reflexivity. In your proof, we use induction on $a$, but then we do not need to use induction on $b$ and $c$ because we can finish the proof simply using other methods. We could have used induction on $b$ and $c$, and ...


2

If you are allowed to use the master theorem then you can immediately conclude that $T(n)=\Theta(n)$ (since $n^{\log_2 2} = n = \omega(1)$). If you are not allowed to use the master theorem then you can write this recurrence instead: $$ T(n) \le 2T(\lfloor n/2 \rfloor) + c, $$ where $c > 0$ is an absolute constant and $T(1) \le c$. Then you can prove by ...


Top 50 recent answers are included