isnt O(nĀ³) usually simplified to O(nĀ²) anyway ?
Yes. The other answer is technically correct, but yours is pragmatically correct.
If a solution is worse than O(nln(n))* then most of us are going to be looking for a pragmatic and completely alternate way to deal with it, rather than analyzing how to make it mildly less terrible.
So Iām just writing O(n^2) as a quick professional replacement for my original write in answer of ādogshitā.
No, nĀ³ cannot be O(nĀ²) as otherwise that would mean that there exists a positive constant K and a positive threshold m such that for any integer n greater than m you would have nĀ³ less than K*nĀ², which would be the same as saying n less than K, which cannot hold for any integer n greater than m. So nĀ³ cannot be an O(nĀ²), which means that something that is an O(nĀ³) is not necessarily an O(nĀ²).
Itās the other way around, if something is an O(nĀ²) then it is necessarily also an O(nĀ³).
Any algorithm can be O(n^2) if you only want it to be occasionally right.
Yes.
And depending how occasionally weāre talking, I can code for some very fast solutions when the correctness requirements are low enough.
Alternately, if we want it to only be occasionally fast, Iāve got a very nice looking and very wrong algorithm for that, as well.
Impressive, very nice. Now letās see LLMās space complexity.