News for hackers. Stuff that matters.
Re:Exploring Clang/LLVM optimization on programming horror by martincmartin on Tuesday August 17, 2021 @06:25PM (#28215508)
you get a linear time O(n) isEven function

In complexity theory, the size of a problem is the number of bits to represent the input, so if the input integer is i, then the size is n = log_2(i) so the algorithm is actually exponential in the number of bits it takes to represent the input.

Re:Exploring Clang/LLVM optimization on programming horror by dragontamer on Tuesday August 17, 2021 @06:30PM (#28215542)
In a strict sense, you're right.

But in practice, you're not. Case in point: matrix multiplication is commonly quoted as O(n^3) (naive), when in fact, the amount of data used is O(n^2), and therefore should be quoted as O(size^2) (quadratic) with respect to data-size. (EDIT: was bad at math for a second).

But no, people mean "n-by-n matrix" has "O(n^3) naive" implementation. In practice, the "n" is just whatever is most convenient for a problem.

In many cases, n is proportional to the input size. But in other cases (such as the famous matrix multiplication examples), n is the sqrt(input-size).

Re:Exploring Clang/LLVM optimization on programming horror by jcranmer on Tuesday August 17, 2021 @08:05PM (#28216232)
> therefore should be quoted as O(size^2) (quadratic)

It's actually O(size^1.5), not O(size^2). Well, assuming you're talking about θ(n) when you mean O(n) as most people do.

[If you're not familiar with the difference, Θ(f(n)) means a function that grows as fast as f(n), up to a constant, whereas O(f(n)) is a function that grows no faster. So n^2 is O(n^3) but not Θ(n^3).]

Re:Exploring Clang/LLVM optimization on programming horror by wittycardio on Tuesday August 17, 2021 @08:08PM (#28216254)
But it's actually quite relevant here. For example with the informal notation you can find all the prime factors of a number N in "O(N)" time , if someone doesn't understand the distinction then they might believe that theres a polytime algorithm for factorization.
Re:Exploring Clang/LLVM optimization on programming horror by trias on Tuesday August 17, 2021 @06:28PM (#28215531)
is complexity theory constrained to binary representations? Why should it?
Re:Exploring Clang/LLVM optimization on programming horror by Ar-Curunir on Tuesday August 17, 2021 @07:10PM (#28215840)
Every base except unary is a constant-factor away from binary, and so is irrelevant asymptotically. We don't use unary because it's artificially slow.
Re:Exploring Clang/LLVM optimization on programming horror by creata on Tuesday August 17, 2021 @09:35PM (#28216823)
Re:Exploring Clang/LLVM optimization on programming horror by Ar-Curunir on Wednesday August 18, 2021 @11:05AM (#28222079)
That post is a joke, right?