-2
$\begingroup$

Does $2^{log_2{n}}$ grow faster than a polynomial? I know that $2^{log_2{n}}$ can be simplified as $n$ but can it be considered as an exponential?

$\endgroup$
1
  • $\begingroup$ Welcome to Computer Theory SE! This is a collaborative website to discuss RESEARCH LEVEL questions in Theoretical Computer Science. Your question is definitely not of a research level, you might want to discuss it on another forum. $\endgroup$
    – J..y B..y
    Aug 25, 2023 at 11:16

1 Answer 1

1
$\begingroup$

As you mention, $2^{\log_2 n} = n$, so it does not grow faster than every polynomial. It doesn't even grow faster than the polynomial $f(n)=n$. So it is not considered to be an exponential function in $n$. However, it is an exponential function of $\log_2 n$. When talking about the time complexity of an algorithm, we consider the running time as a function of the size of the input. So if your input is a single integer $n$, then the size of your input is $\log_2 n$ (since that is the number of bits needed to write $n$). Thus an algorithm with running time $2^{\log_2 n}$ in this situation would be considered an exponential time algorithm.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.