Post History
#3: Post edited
by
alx
·
2026-03-27T15:40:35Z (6 months ago)
- 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 (actually, quasi-polynomial)?
- 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)?
#2: Post edited
by
alx
·
2026-03-27T15:40:17Z (6 months ago)
- 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)))`?
- 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 (actually, quasi-polynomial)?
#1: Initial revision
by
alx
·
2026-03-27T15:12:47Z (6 months ago)
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)))`?