# 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 < 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.

The error is where you claim that $$kn=n^c$$ where $$0. 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.)
• But I can pick $c, k ∈ R$ where $kn = n^c$, right? For example $k=0.1, n=100, c=0.5$ Is this not true for all $n, c$, and $k$? – garbagecollector Aug 31 '19 at 5:19
• @garbagecollector, no. I suggest spending some time with the definition of big-O notation. ($c$ is not allowed to depend on $n$.) This platform isn't well-suited for interactive tutoring, unfortunately. – D.W. Aug 31 '19 at 5:22