Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$

Question

I am trying to see if a recurrence relation where $f(n)$ has some constant factor $k$, e.g. $f(n)=kn$ where $0 < k < 1$, is $O(n)$. I am reaching a different result depending which route I take. Given the following recurrence relation:

$$T(n)=2T(\frac{n}{2})+f(n)$$ $$T(n)=2T(\frac{n}{2})+kn$$ Since $0 < k < 1$, we can represent $kn=n^c$, where $0 < c < 1$

This falls under the case 1 of the Master Theorem, because $a=2, b=2$, and therefore $log_b a = log_2 2 = 1 > c$.

It's $O(n)$.

But if I try to unfold the recurrence: $$\begin{split}T(n) & = 2T(\frac{n}{2})+kn \\ & = 4T(\frac{n}{4})+2kn \\ & = 8T(\frac{n}{8})+3kn \\ & = ... \\ & = 2^cT(\frac{n}{2^c})+ckn \\ \end{split}$$

When $\frac{n}{2^c}=1$, $n=2^c$, then $log_2 n = c$.

So now it's $T(n) = nT(1) + kn log_2 n$, which is $O(n log_2 n)$. Now I am confused.

Answer 1

The error is where you claim that $kn=n^c$ where $0<c<1$. This is not correct. Even when $k<1$, it is still the case that $kn=\Theta(n)$; it is not $O(n^c)$ for any $c<1$. (Check the definition of big-O notation.)