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)$?

  • 2
    $\begingroup$ 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$. $\endgroup$ – plop Mar 11 at 18:30
  • $\begingroup$ 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$. $\endgroup$ – plop Mar 11 at 18:37
  • $\begingroup$ @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$. $\endgroup$ – harshatech2012 Mar 12 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.