6 ms·
This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) I
by ihaveajob 7y ago
This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.
- Google234 7y ago2^2^9 is 1.340781e+154
- mathgladiator 7y agoIn this format, exponents are evaluated left to right, so this is 4^9 which is 262144 and is reasonable.
- vecter 7y agoThat's certainly not the standard. If anything, exponentiation is usually performed right to left, with some exceptions [0]. However, the fact that we even have carets in this conversation isn't because the GP wanted to adopt a left-to-right convention, but due to limitations in the richness of HN's text editor. If you write a tower of 2^2^9 on a whiteboard and ask 1000 mathematicians and computer scientists to evaluate it, I'm sure 999 or 1000 of them would evaluate it as 2^(2^9). [0] https://en.wikipedia.org/wiki/Order_of_operations#Serial_exponentiation https://en.wikipedia.org/wiki/Order_of_operations#Serial_exp...
- mathgladiator 7y agoI'm a mathematician and a computer scientist, so I must be one in a thousand. The link even indicates that ambiguity exists in wild, and I think clear notation would help. In this case, the absurdity of the number suggests a more realistic number.
- vecter 7y agoDon't you think it's more likely that the original poster made a mistake and that a graph algorithm isn't actually O(2^2^n)? I can't name a single meaningful algorithm that has that time complexity.
- umanwizard 7y agoA good mnemonic is that a^b^c normally associates to the right because if you meant (a^b)^c, you could have just written a^(bc).
- kachnuv_ocasek 7y agoBut that would not be hyperexponential as GP claimed.
- vecter 7y agoCould you explain more? As the other commenter pointed out, 2^2^9 = 2^512 which is an astronomically large number (far more than the number of atoms of ordinary matter in the observable universe). Something doesn't seem right.
- actuator 7y agoMust be a typo. Since he was working with graph and I am assuming the problem is NP hard. Probably was of the order of 2^9
- vecter 7y agoI'm inclined to agree with you, but the GP said "hyper-exponential", whatever that even means.
- mathgladiator 7y agoWhy couldn't it be (2^2)^9 = 4^9 = 262144 ?