News for hackers. Stuff that matters.
Re:Big O Notation – Explained as easily as possible by alok-g on Saturday January 16, 2021 @01:20PM (#25804109)
>> 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?

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.