# Polynomial vs. Exponential Time Complexity [closed]

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?

• 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. Aug 25, 2023 at 11:16

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.