Return to 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 recurrennce: $$\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 n)$. Now I am confused.

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.

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 think I reach that conclusion, but I want to double check to make sure. 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)$.

Is this correct? Is there another way to prove this?

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 recurrennce: $$\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 n)$. Now I am confused.

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 think I reach that conclusion, but I want to double check to make sure. 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$

Therefore, 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$.

Therefore, it's $O(n)$.

Is this correct? Is there another way to prove this?

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 think I reach that conclusion, but I want to double check to make sure. 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)$.

Is this correct? Is there another way to prove this?