Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$ I am trying to see if a recurrence relation where $f(n)$ has some constant factor $k$, e.g. $f(n)=kn$ where $0 &lt; k &lt; 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 &lt; k &lt; 1$, we can represent $kn=n^c$, where $0 &lt; c &lt; 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 &gt; c$.

It's $O(n)$.

But if I try to unfold the recurrence:
$$\begin{split}T(n) &amp; = 2T(\frac{n}{2})+kn \\
&amp; = 4T(\frac{n}{4})+2kn \\
&amp; = 8T(\frac{n}{8})+3kn \\
&amp; = ... \\
&amp; = 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.
The error is where you claim that $kn=n^c$ where $0&lt;c&lt;1$.  This is not correct.    Even when $k&lt;1$, it is still the case that $kn=\Theta(n)$; it is not $O(n^c)$ for any $c&lt;1$.  (Check the definition of big-O notation.)