Post History
#2: Post edited
by
clemens
·
2026-03-28T02:59:59Z (6 months ago)
- This is not entirely correct. An algorithm is $\Theta(f(n))$ if, asymptotically, it is within some constant factor of $f$. Thus we cannot simply add or take away constant factors from within an exponential.
- We *can*, however, do so if we talk about the *log* of running time, which is $\Theta(\log(n) \log(\log(n)))$.
I _think_ (but am not sure that) it's also not atypical, in such cases, to say that the algorithm is $\Theta(n^{C \log(\log(n))})$---not indicating by this a *particular* C but merely saying that the algorithm grows *faster* than $n^{C \log(\log(n))}$ for some low value of $C$ and *slower* than $n^{C \log(\log(n))}$ for some high value of $C$.
- This is not entirely correct. An algorithm is $\Theta(f(n))$ if, asymptotically, it is within some constant factor of $f$. Thus we cannot simply add or take away constant factors from within an exponential.
- We *can*, however, do so if we talk about the *log* of running time, which is $\Theta(\log(n) \log(\log(n)))$.
- I _think_ (but am not sure that) it's also not atypical, in such cases, to say that the algorithm is $\Theta(n^{C \log(\log(n))})$---not indicating by this a *particular* C but merely saying that the algorithm grows *faster* than $n^{C \log(\log(n))}$ for some low value of $C$ and *slower* than $n^{C \log(\log(n))}$ for some high value of $C$.
- As alx commented we can say more tersely that the algorithm is quasipolynomial; indeed it is below $e^{\log(n)^2}$ and thus a "relatively fast" quasipolynomial algorithm.
#1: Initial revision
by
clemens
·
2026-03-27T21:05:27Z (6 months ago)
This is not entirely correct. An algorithm is $\Theta(f(n))$ if, asymptotically, it is within some constant factor of $f$. Thus we cannot simply add or take away constant factors from within an exponential.
We *can*, however, do so if we talk about the *log* of running time, which is $\Theta(\log(n) \log(\log(n)))$.
I _think_ (but am not sure that) it's also not atypical, in such cases, to say that the algorithm is $\Theta(n^{C \log(\log(n))})$---not indicating by this a *particular* C but merely saying that the algorithm grows *faster* than $n^{C \log(\log(n))}$ for some low value of $C$ and *slower* than $n^{C \log(\log(n))}$ for some high value of $C$.