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³).
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".
15 Comments
spread@programming.dev · 32 pts · 3y
Impressive, very nice. Now let's see LLM's space complexity.
fubo@lemmy.world · 27 pts · 3y
O(all the GPUs, all of them)VictorPrincipum@vlemmy.net · 11 pts · 3y
Hey now, don’t forget all the memory too
rcmaehl@lemmy.world · 11 pts · 3y
And my cache!
Sotuanduso@lemm.ee · 2 pts · 3y
/UnexpectedGimli
whiskeypickle@lemmy.ml · 5 pts · 3y
Eggshell… and is that… Gothic type?
duncesplayed@lemmy.one · 17 pts · 3y
Any algorithm can be O(n^2) if you only want it to be occasionally right.
Iridium@lemmy.world · 18 pts · 3y
Accurate for almost 100% of cases
darcy@sh.itjust.works · 2 pts · 3y
as test count approach infinity
julianh@lemm.ee · 5 pts · 3y
Any algorithm can be O(1) if you cache all the answers beforehand.
MajorHavoc@lemmy.world · 2 pts · 3y
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.
darcy@sh.itjust.works · 2 pts · 3y
isnt O(n³) usually simplified to O(n²) anyway ?
AlmightySnoo@lemmy.world · 3 pts · 3y
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³).
darcy@sh.itjust.works · 2 pts · 3y
ok thanks
MajorHavoc@lemmy.world · 2 pts · 3y
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".