<p>As you mention, <span class="math-container">$2^{\log_2 n} = n$</span>, so it does not grow faster than every polynomial. It doesn't even grow faster than the polynomial <span class="math-container">$f(n)=n$</span>. So it is not considered to be an exponential function in <span class="math-container">$n$</span>. However, it is an exponential function of <span class="math-container">$\log_2 n$</span>. 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 <span class="math-container">$n$</span>, then the size of your input is <span class="math-container">$\log_2 n$</span> (since that is the number of bits needed to write <span class="math-container">$n$</span>). Thus an algorithm with running time <span class="math-container">$2^{\log_2 n}$</span> in this situation would be considered an exponential time algorithm.</p>

CC BY-SA 4.0
2023-08-25T00:12:02.793Z
2023-08-25T00:12:02.793Z
NaturalLogZ
<p>Does <span class="math-container">$2^{log_2{n}}$</span> grow faster than a polynomial? I know that <span class="math-container">$2^{log_2{n}}$</span> can be simplified as <span class="math-container">$n$</span> but can it be considered as an exponential?</p>

CC BY-SA 4.0
2023-08-25T11:16:58.873Z
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.
J.y B.y
<time-complexity><polynomial-time>
Polynomial vs. Exponential Time Complexity
Janet Stewart
# Polynomial vs. Exponential Time Complexity

(Asked by: username_0 on 2023-08-24)

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?

**Tags:** time-complexity, polynomial-time

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2023-08-25. Score: 1

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.


---

