4 ms·

>> If you consider "addition" to be 1 operation then ... What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for

by alok-g 6y ago

>> If you consider "addition" to be 1 operation then ... What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for numbers, e.g., a 32-bit signed integer. How would we reformulate or express algorithmic complexity if we were to talk about unbounded integer values or infinite-precision mathematics?

mhh__ 6y ago
You'd need to know the exact details of the implementation of your arithmetic library, but it would depend on the integer in question which makes analysis a little harder so adding two numbers would become some function O(f(n, m)) where n, m are the two numbers or some property of them (length, digits etc.)
qsort 6y ago
It generally changes the analysis very little but makes it more annoying, which is why arithmetic is usually taken to be O(1). Formally speaking you'd have to specify a computational model to be able to talk about complexity (there is no such thing as 'complexity' but only 'complexity respective to a model'; e.g. you can change the big-O complexity on Turing machines by using more tapes). The computational model of a book like CLRS is "arithmetic is O(1), but we're not going to abuse that bug".
aweinstock 6y ago
The contrast between Gauss-Jordan[0] and the Bareiss algorithm[1] is a good example of explicitly handling the length of the numbers in bits as part of the runtime. Gauss-Jordan is O(n^3) if you consider addition and multiplication to be constant-time, but if it operates on arbitrary-precision integers, it can get exponentially slow[2]. The Bareiss algorithm avoids this worst-case behavior by choosing the pivots in a slightly more involved manner, which avoids building up large intermediate values. [0]: https://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency https://en.wikipedia.org/wiki/Gaussian_elimination#Computati... [1]: https://en.wikipedia.org/wiki/Bareiss_algorithm https://en.wikipedia.org/wiki/Bareiss_algorithm [2]: https://staff.itee.uq.edu.au/havas/fh97.pdf https://staff.itee.uq.edu.au/havas/fh97.pdf, Section 3.1's "Construction A" is a specific matrix that exhibits the worst-case behavior.
Brian_K_White 6y ago
Then just substitute whatever other operation that makes you happy? Or an imaginary one if you mean to say there is no such thing in real hardware.

by alok-g 6y ago

mhh__ 6y ago

You'd need to know the exact details of the implementation of your arithmetic library, but it would depend on the integer in question which makes analysis a little harder so adding two numbers would become some function O(f(n, m)) where n, m are the two numbers or some property of them (length, digits etc.)

qsort 6y ago

It generally changes the analysis very little but makes it more annoying, which is why arithmetic is usually taken to be O(1). Formally speaking you'd have to specify a computational model to be able to talk about complexity (there is no such thing as 'complexity' but only 'complexity respective to a model'; e.g. you can change the big-O complexity on Turing machines by using more tapes). The computational model of a book like CLRS is "arithmetic is O(1), but we're not going to abuse that bug".

aweinstock 6y ago

The contrast between Gauss-Jordan[0] and the Bareiss algorithm[1] is a good example of explicitly handling the length of the numbers in bits as part of the runtime. Gauss-Jordan is O(n^3) if you consider addition and multiplication to be constant-time, but if it operates on arbitrary-precision integers, it can get exponentially slow[2]. The Bareiss algorithm avoids this worst-case behavior by choosing the pivots in a slightly more involved manner, which avoids building up large intermediate values. [0]: https://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency https://en.wikipedia.org/wiki/Gaussian_elimination#Computati... [1]: https://en.wikipedia.org/wiki/Bareiss_algorithm https://en.wikipedia.org/wiki/Bareiss_algorithm [2]: https://staff.itee.uq.edu.au/havas/fh97.pdf https://staff.itee.uq.edu.au/havas/fh97.pdf, Section 3.1's "Construction A" is a specific matrix that exhibits the worst-case behavior.

Brian_K_White 6y ago

Then just substitute whatever other operation that makes you happy? Or an imaginary one if you mean to say there is no such thing in real hardware.