Upper bound of the complexity of an algorithm on two variables
I've determined the complexity of an algorithm to be
sqrt(2*pi/e)
* (log(n)/log(1/1-p) /e) ^ (log(n)/log(1/p) + 1)
/ sqrt(log(n)/log(1/p))
Where the variables are:
n: the input size; it's an integer >=1.
p: a coefficient in the range (0, 1).
The plots show that the worst case of p is moving. It initially grows (for n<10^5 or so), with a maximum at p=0.95 or so, and then decreases slowly (but remaining above 0.5, or so it seems). For most of the curve, we can approximate it as p=0.9, and consider it fixed.
Thus, for the worst case, the only variable seems to be n.
Let's hide the constants (or almost constants) (every C is a different C):
C * (C*log(n)) ^ (C*log(n) + C) / sqrt(C*log(n))
Am I right considering this algorithm to be in O((log(n))^(log(n))) and thus sub-exponential (more precisely, quasi-polynomial)?
1 answer
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| alx | (no comment) | Mar 27, 2026 at 22:58 |
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.
2 comment threads
0 comment threads