News for hackers. Stuff that matters.
Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Tuesday December 15, 2015 @05:12PM (#10740861)
When people want to use big-O notation, they use limits that dominate both for astronomical values of n, and for realistic values of n. Making those diverge is intentional obfuscation.

More importantly, you ignore the nature of the problem when you treat 2^64 as a constant, but the number of values in the list as n. I'm comfortable betting that if you take this problem, and push n to 2^100, you'll find that your integer size has been changed to 2^128. In other words, iconjack's algorithm is actually O(n) space or worse.

Re:Calculating integer factorials in constant time, taking a... by evanpw on Tuesday December 15, 2015 @06:04PM (#10741130)
> Making those diverge is intentional obfuscation.

It's not obfuscation, it's literally the definition.

I'm not saying that the algorithm in question is practical, but asymptotic complexity has a precise mathematical definition, so it's totally possible for an algorithm with "good" time complexity to be so complicated or have such a huge constant that it's impossible to use (see [1] and [2] for some examples).

It's also totally legitimate to give a constraint on additional memory size, so that this algorithm is disallowed altogether (which is probably the right answer), or change the problem so that the word size varies with the list length, but it's not legitimate to just say that the algorithm isn't linear time because the constant is too big.

[1] http://cstheory.stackexchange.com/questions/4491/powerful-al...

[2] https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Tuesday December 15, 2015 @06:22PM (#10741222)
The definition talks about what happens for extremely large numbers.

It does not talk about smaller numbers at all.

If you use an algorithm and complexity that are close for both moderately large numbers and extremely large numbers, you've done a good job.

If you introduce dumb things like constants that are larger than the known universe, you are performing obfuscation.

The suggested algorithm is linear, but only when applied to a very specific interpretation of the problem. I'm disagreeing with that interpretation of the problem, not the conclusion that it's linear within that particular interpretation.