# substitution method - proving karatsuba algorithm is not O(n)

I want to prove that $$T(n) \neq O(n)$$ for the Karatsuba algorithm, which has the following recurrence:

$$T(n) = \begin{cases} k_1, & \text{if n = 1} \\ 3T(n/2) + k_2n, & \text{if n \gt 1} \end{cases}$$

where, $$k_1$$ and $$k_2$$ are constants, such that $$k_1 \gt 0$$ and $$k_2 \in \mathbb R$$.

So, to prove that $$T(n) \neq O(n)$$, I did the following:
Inductive hypothesis: $$\exists c, n_o \gt 0$$ such that $$T(n) \leq cn \quad, \forall n \geq n_o$$
Base case: at $$n = 1$$, we get the following constraint: $$T(1) = k_1 \leq c$$, which holds for $$c \geq k_1$$
Inductive case: assuming that $$T(n/2) \leq {cn\over2}$$, we have \begin{align} T(n) \quad &\leq 3({cn\over2}) + k_2n \\ &= cn + ({c\over2} + k_2)n \\ \end{align}

But, for $$cn + ({c\over2} + k_2)n \leq cn$$ to hold, $${c\over2} + k_2 \leq 0$$. Although, this inequality doesn't hold for $$k_2 \geq 0$$ (since $$c > 0$$), it does hold if $$c \leq -2k_2$$ and $$k_2 < 0$$.

Hence, I am having difficulty concluding that $$T(n) \neq O(n)$$. Is there anything wrong with the induction? And also, then how to prove that $$T(n) \neq O(n)$$?

• You are trying to build a proof by induction, but that is useful if you are proving that $T(n)\leq cn$ for all large $n$. If the proof fails, that tells you nothing about the result. What you should show is the existence of a sequence $n_1,n_2,...$ such that for all $c>0$ there is a $k$ such that $T(n_k)>cn_k$. – plop Mar 11 at 18:30
• Since you have that repeated division by $2$ in $T(n/2)$, it is probably convenient to look at what happens with $n_k=2^k$. Plugging it in the recurrence you get $T(2^k)=3T(2^{k-1})+k_22^k=3^2T(2^{k-2})+k_2(32^{k-1}+2^{k})=...=3^k k_1+k_2(3^{k-1}2+3^{k-2}2^2+...+2^{k})>3^kk_1$. This, in turn becomes larger than $c2^k=cn_k$ for sufficiently large $k$. – plop Mar 11 at 18:37
• @plop - Based on your comment, is the following reasoning correct: proving that $T(n) \in \omega(n)$ would mean that $T(n) \notin O(n)$ since the latter would contradict $\lim\limits_{n \to \infty} \frac{T(n)}{cn} = \infty$. – harshatech2012 Mar 12 at 13:42