7 ms·

If you enforce n<=12 (to prevent undefined behavior) in the original "naive" algorithm, then it too is constant time, i.e., O(12).

iconjack 11y ago
That's right, if there's a limit on n, then your algorithm is O(n). I took some downvotes when I made this point on StackOverflow: http://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list/1587119#1587119 http://stackoverflow.com/questions/1586858/find-the-smallest...
- Dylan16807 11y ago
  That's because 2^64 is naturally represented as 2^n, while you're representing it as n. You can technically define n as whatever you want, but if you don't follow certain conventions you will face opposition. n as 12 makes a lot of sense. n as a number too large to count doesn't make sense in the context of real programs.
  - evanpw 11y ago
    > You can technically define n as whatever you want The formal definition of time complexity measures relative to the size of the input, which in this case would be proportional to the number of elements in the list. > n as a number too large to count doesn't make sense in the context of real programs The definition of big-O notation involves taking the limit as n goes to infinity. It doesn't really even make sense if you only have a finite (even if huge) number of problem instances, since then everything is bounded by a constant.
    - Dylan16807 11y ago
      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.
      - evanpw 11y ago
        > 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-algorithms-too-complex-to-implement http://cstheory.stackexchange.com/questions/4491/powerful-al... [2] https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
        Dylan16807 11y ago
        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.
Dylan16807 11y ago
Constant time goes beyond O(1), it means that the lower bound is equal to the upper bound. 10! can't be faster than 12!
- tantalor 11y ago
  No, I don't think so. O(1) is "constant" time. See https://en.wikipedia.org/wiki/Time_complexity https://en.wikipedia.org/wiki/Time_complexity
  - Dylan16807 11y ago
    O(1) is a constant time bound. But when people talk about constant time they often mean literally constant, such as to avoid timing attacks.
    - dragonwriter 11y ago
      Its true that constant time is sometimes used in that way, though in discussions of computation complexity, "constant time" usually means O(1). There narrower use is more like Θ(1) with the upper and lower constants identical.
- uxcn 11y ago
  This isn't correct. Consider an algorithm that special cases powers of two for dividing a number. Both cases take a constant number of steps, although dividing by a power of two is fewer. The lower and upper bound differ, but they are both still constant.
  - Dylan16807 11y ago
    asymptotically constant != constant
    - uxcn 11y ago
      Asymptotically constant is what we normally talk about in relation to constant time. An algorithm that always runs in n steps with respect to input would be considered constant given the definition you're using, which would at very least be confusing. It's also difficult to talk about constant time outside of an asymptotic context. There are a number of subtle sources for timing variances (e.g. branches, branch mispredicts, cache misses, pipeline stalls, context switches, etc..).

iconjack 11y ago

That's right, if there's a limit on n, then your algorithm is O(n). I took some downvotes when I made this point on StackOverflow: http://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list/1587119#1587119 http://stackoverflow.com/questions/1586858/find-the-smallest...

Dylan16807 11y ago
That's because 2^64 is naturally represented as 2^n, while you're representing it as n. You can technically define n as whatever you want, but if you don't follow certain conventions you will face opposition. n as 12 makes a lot of sense. n as a number too large to count doesn't make sense in the context of real programs.
- evanpw 11y ago
  > You can technically define n as whatever you want The formal definition of time complexity measures relative to the size of the input, which in this case would be proportional to the number of elements in the list. > n as a number too large to count doesn't make sense in the context of real programs The definition of big-O notation involves taking the limit as n goes to infinity. It doesn't really even make sense if you only have a finite (even if huge) number of problem instances, since then everything is bounded by a constant.
  - Dylan16807 11y ago
    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.
    - evanpw 11y ago
      > 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-algorithms-too-complex-to-implement http://cstheory.stackexchange.com/questions/4491/powerful-al... [2] https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
      - Dylan16807 11y ago
        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.

Dylan16807 11y ago

Constant time goes beyond O(1), it means that the lower bound is equal to the upper bound. 10! can't be faster than 12!

tantalor 11y ago
No, I don't think so. O(1) is "constant" time. See https://en.wikipedia.org/wiki/Time_complexity https://en.wikipedia.org/wiki/Time_complexity
- Dylan16807 11y ago
  O(1) is a constant time bound. But when people talk about constant time they often mean literally constant, such as to avoid timing attacks.
  - dragonwriter 11y ago
    Its true that constant time is sometimes used in that way, though in discussions of computation complexity, "constant time" usually means O(1). There narrower use is more like Θ(1) with the upper and lower constants identical.
uxcn 11y ago
This isn't correct. Consider an algorithm that special cases powers of two for dividing a number. Both cases take a constant number of steps, although dividing by a power of two is fewer. The lower and upper bound differ, but they are both still constant.
- Dylan16807 11y ago
  asymptotically constant != constant
  - uxcn 11y ago
    Asymptotically constant is what we normally talk about in relation to constant time. An algorithm that always runs in n steps with respect to input would be considered constant given the definition you're using, which would at very least be confusing. It's also difficult to talk about constant time outside of an asymptotic context. There are a number of subtle sources for timing variances (e.g. branches, branch mispredicts, cache misses, pipeline stalls, context switches, etc..).