Is $ 2 ^ { \log _ 3 n + 1 } $ linear running time?

Question

Today, our professor said that $ 2 ^ { \log _ 3 n + 1 } $ is linear running time. I did not understand why. Can someone explain this to me? Thanks

Answer 1

Note $2^{\log_3 n+1}= 2(3^{\log_3 2})^{\log_3 n}=2n^{{\log_3 2}}$ and ${\log_3 2}< 1$. So it is bounded by a linear function in $n$.

Answer 2

It's not linear, it's sublinear. $2^{\log_3(n)} = n^{\log(3)(2)} \approx n^{0.6309}$.

Answer 3

$O(2^{log_3 n +1}) = O(2^{log_3 n}) = O(2^{\frac{log_2 n}{log_2 3}}) = O(n^{log_3 2})$ which is not linear.

Answer 4

Somewhere along the way, it may have become confused as to whether "linear time" means $\Theta(n)$, i.e. bounded above by $cn$ and bounded below by $dn$ where $c,d$ are positive constants, or whether is merely means $O(n)$, i.e. bounded above by $cn$ where $c$ is a positive constant. Your stated running time is $O(n)$ but not $\Theta(n)$, as shown in other answers.

Answer 5

Sublinear is linear, like as $n \in O(n^2)$. So $O(2^{\log_3(n)+1})=O(n^{\log_3 2})=O(n).$

Answer 6

Meh. This could be wrong, and if it is, feel free to correct me! This isn't linear time. Here's is why:

$2^{{\log_{3} n}+1} = 2^{\frac{log_2 n}{log_2 3}+1} $

And I think this is..like the..same as this:

$2(2^{log_2 n})^{\frac {1}{log_2 3}} = 2n^{\frac {1}{log_2 3}}$

And, if I'm not mistaken: $\frac {1} {log_2 3} < 1 \rightarrow n^{\frac {1} {log_2 3}} < n$

So it appears to me that it is actually faster than linear time :D But I guess technically you could consider this as running in linear time since you could say its upper bound is linear time. :D