Comments on Upper bound of the complexity of an algorithm on two variables
Parent
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)?
Post
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