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).]
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).]