Re:Big O Notation – Explained as easily as possible
by aweinstock on Saturday January 16, 2021 @02:05PM
(#25804497)
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#Computati... [1]: https://en.wikipedia.org/wiki/Bareiss_algorithm [2]: 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.
Re:Big O Notation – Explained as easily as possible
by qsort on Saturday January 16, 2021 @01:48PM
(#25804333)
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".
Re:Big O Notation – Explained as easily as possible
by mhh__ on Saturday January 16, 2021 @01:26PM
(#25804158)
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.)
Re:Big O Notation – Explained as easily as possible
by Brian_K_White on Saturday January 16, 2021 @03:45PM
(#25805344)
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.
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?