Solve the recurrence $$A(n) = 2A(n/2) + O(1)\,.$$
I have done the following:
I have guessed the result to be $\Omega(n)$
Hypothesis: For $k < n$, $$A(k) \geq c k\,.$$
Substitution: $$A(n) \geq 2c(n/2) + O(1) = A(n) \geq 2c(n/2) + d\,.$$
Simplify: $$A(n) \geq cn + d\,.$$
What to do now?
Let $A(n)=2\,A\left(\frac{n}{2}\right)+c_n$. If $a\leq c_n\leq b$ for all $n$, then by induction (or via telescopic sum), one can show that $$2^k\,A(1)+(2^k-1)a\leq A(2^k) \leq 2^k\,A(1)+(2^k-1)b\,.$$ This means $$\liminf_{k\to\infty}\frac{A(2^k)}{2^k}\geq A(1)+a\text{ and }\limsup_{k\to\infty}\,\frac{A(2^k)}{2^k}\leq A(1)+b\,.$$
It is not true that $A(n)=\Omega(n)$ in all cases, though. In the unlucky case, where $a=b=-A(1)$, we get $A(2^k)=A(1)$ for all $k$. Thus, $$\liminf_{n\to\infty}\,\left|\frac{A(n)}{n}\right|=0\,.$$