6 ms·

>...where I discover the hidden complexity of a simple programming problem. I thought it was very ironic that soon after that sentence, the author claims the a

>...where I discover the hidden complexity of a simple programming problem. I thought it was very ironic that soon after that sentence, the author claims the arithmeticSum method is O(1) when it is actually O(log(n) log(log(n))). Many people seem to assume that multiplication is a constant time operation. There is actually immense "hidden complexity" in doing multiplication of arbitrarily large integers efficiently. David Harvey proved last year that multiplication of two n bit integers can be done in O(n log n). It is still an open conjecture that this is the best possible.

dahart 7y ago
You’re right, and it’s a good point, but I think you’re too hard on the author and other people. > the author claims the arithmeticSum method is O(1) He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on computers that support arbitrarily large numbers. > Many people seem to assume that multiplication is a constant time operation. Multiplication is constant time for the built-in data types, for any 64-bit ints or doubles. It’s okay to call it constant until you use huge number methods.
- rwbhn 7y ago
  But the author follows that with "It works the same way for 100 as it does 10e100."
  - dahart 7y ago
    True! That statement does follows the math formula, and by itself the statement is true regardless of complexity. It will work the same way for small numbers as large ones. The 10e100 comment does precede the implementation, and this particular O(1) implementation of course might not support inputs in the range of 10e100 exactly.
- Ragib_Zaman 7y ago
  I disagree. Why would it be reasonable to assume "multiplication without a specific implementation is constant"? By definition, Big-O complexity describes what happens as a certain parameter gets arbitrarily large. If we say "ok but if we restrict that parameter to common sizes, it's actually O(1)", then everything is O(1). There is some constant C where Bubble sort will sort any array that fits into your RAM within C seconds, so is it okay to call Bubble sort constant time until you use huge array methods that process arrays on your hard drive?
  - dahart 7y ago
    By definition, big-O is for predicting the run-time growth of a specific implementation. It doesn’t directly apply to formulas. And it’s not an abstract concept that applies to arbitrary inputs that the program you’re analyzing can’t process by design. You cannot assume arbitrarily large inputs. The reason 64 bit mults are constant is because we have a hardware implementation of multiplication that has a constant predictable run time. When you use the built-in mults, you get to use O(1) for the purposes of your complexity analysis in return for a hard limit on the size of numbers you can multiply. Your bubble sort example is contrived, but the answer is that it is okay to call a sort of 10 elements constant if that’s one component of a system and it doesn’t grow as the size of your input grows. The point of big-O is to understand the run time growth of your program, and if the sort inside doesn’t change as your input changes, then that piece is constant.
    - Ragib_Zaman 7y ago
      >By definition, big-O is for predicting the run-time growth of a specific implementation. It doesn’t directly apply to formulas. And it’s not an abstract concept that applies to arbitrary inputs that the program you’re analyzing can’t process by design. You cannot assume arbitrarily large inputs. Time complexity is usually for specific algorithms, though it can also be studied for a general problem itself (e.g. any comparison sort is at least O(n log n), regardless of algorithm or implementation). It is precisely a concept that applies to arbitrarily large inputs, that condition is at the core of its very definition. If I designed a hardware board that runs bubble sort on any array that fits into its 16GB of memory and gave documentation printing out its (large) constant predictable run time, that still wouldn't make it correct to say Bubble sort is a constant time operation. >Your bubble sort example is contrived, but the answer is that it is okay to call a sort of 10 elements constant if that’s one component of a system and it doesn’t grow as the size of your input grows...if the sort inside doesn’t change as your input changes, then that piece is constant. We aren't talking about running on 10 elements and it staying at 10 elements as the size of the input grows (that would indeed be O(1)). For the original example in the link, we are talking about a piece (arithmeticSum) whose input is n, which tautologically does grow as the size of the input grows.
evanpw 7y ago
This argument comes up all the time, and the answer is that big-O notation is very general, and only makes sense relative to a particular computation model. For example, you may describe a sorting algorithm's complexity by counting the number of comparisons, abstracting away details like memory caching or arbitrarily-sized elements. So it's perfectly reasonable for the original author to call arithmeticSum constant time, assuming that the numbers are bounded, and it's also perfectly reasonable for other researchers to say that multiplication is O(n log n), without that assumption.

dahart 7y ago

You’re right, and it’s a good point, but I think you’re too hard on the author and other people. > the author claims the arithmeticSum method is O(1) He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on computers that support arbitrarily large numbers. > Many people seem to assume that multiplication is a constant time operation. Multiplication is constant time for the built-in data types, for any 64-bit ints or doubles. It’s okay to call it constant until you use huge number methods.

rwbhn 7y ago
But the author follows that with "It works the same way for 100 as it does 10e100."
- dahart 7y ago
  True! That statement does follows the math formula, and by itself the statement is true regardless of complexity. It will work the same way for small numbers as large ones. The 10e100 comment does precede the implementation, and this particular O(1) implementation of course might not support inputs in the range of 10e100 exactly.
Ragib_Zaman 7y ago
I disagree. Why would it be reasonable to assume "multiplication without a specific implementation is constant"? By definition, Big-O complexity describes what happens as a certain parameter gets arbitrarily large. If we say "ok but if we restrict that parameter to common sizes, it's actually O(1)", then everything is O(1). There is some constant C where Bubble sort will sort any array that fits into your RAM within C seconds, so is it okay to call Bubble sort constant time until you use huge array methods that process arrays on your hard drive?
- dahart 7y ago
  By definition, big-O is for predicting the run-time growth of a specific implementation. It doesn’t directly apply to formulas. And it’s not an abstract concept that applies to arbitrary inputs that the program you’re analyzing can’t process by design. You cannot assume arbitrarily large inputs. The reason 64 bit mults are constant is because we have a hardware implementation of multiplication that has a constant predictable run time. When you use the built-in mults, you get to use O(1) for the purposes of your complexity analysis in return for a hard limit on the size of numbers you can multiply. Your bubble sort example is contrived, but the answer is that it is okay to call a sort of 10 elements constant if that’s one component of a system and it doesn’t grow as the size of your input grows. The point of big-O is to understand the run time growth of your program, and if the sort inside doesn’t change as your input changes, then that piece is constant.
  - Ragib_Zaman 7y ago
    >By definition, big-O is for predicting the run-time growth of a specific implementation. It doesn’t directly apply to formulas. And it’s not an abstract concept that applies to arbitrary inputs that the program you’re analyzing can’t process by design. You cannot assume arbitrarily large inputs. Time complexity is usually for specific algorithms, though it can also be studied for a general problem itself (e.g. any comparison sort is at least O(n log n), regardless of algorithm or implementation). It is precisely a concept that applies to arbitrarily large inputs, that condition is at the core of its very definition. If I designed a hardware board that runs bubble sort on any array that fits into its 16GB of memory and gave documentation printing out its (large) constant predictable run time, that still wouldn't make it correct to say Bubble sort is a constant time operation. >Your bubble sort example is contrived, but the answer is that it is okay to call a sort of 10 elements constant if that’s one component of a system and it doesn’t grow as the size of your input grows...if the sort inside doesn’t change as your input changes, then that piece is constant. We aren't talking about running on 10 elements and it staying at 10 elements as the size of the input grows (that would indeed be O(1)). For the original example in the link, we are talking about a piece (arithmeticSum) whose input is n, which tautologically does grow as the size of the input grows.

evanpw 7y ago

This argument comes up all the time, and the answer is that big-O notation is very general, and only makes sense relative to a particular computation model. For example, you may describe a sorting algorithm's complexity by counting the number of comparisons, abstracting away details like memory caching or arbitrarily-sized elements. So it's perfectly reasonable for the original author to call arithmeticSum constant time, assuming that the numbers are bounded, and it's also perfectly reasonable for other researchers to say that multiplication is O(n log n), without that assumption.