Programmer Humor

32410 readers

523 users here now

Post funny things about programming here! (Or just rant about your favourite programming language.)

Rules:

Posts must be relevant to programming, programmers, or computer science.
No NSFW content.
Jokes must be in good taste. No hate speech, bigotry, etc.

founded 5 years ago

MODERATORS

AgreeableLandscape@lemmy.ml

cat_programmer@lemmy.ml

203

Not everything can be done in constant time, that's O(k) (sh.itjust.works)

submitted 4 months ago by alphacyberranger@sh.itjust.works to c/programmerhumor@lemmy.ml

7 comments fedilink hide all child comments

you are viewing a single comment's thread
view the rest of the comments

[–] remi_pan@sh.itjust.works 4 points 4 months ago (2 children)

I know I shouldn't do it here, but let me ask a serious question : does the square in O(n!²) really matter ? I have a confused intuition that the factorial grows so much faster than the square that it kind of disapears assymptoticaly.

[–] DrM@feddit.de 3 points 4 months ago (1 children)

no it's the joke. In o-notation you always use the highest approximation, so o(n!²) does not exist, it's only o(n!)

Otherwise there would never be o(1) or o(n), because o(1) would imply that the algorithm only has a single line of instructions, same for o(n)

[–] Buildout@lemmy.world 7 points 4 months ago

T = O(n) means that there exists a single constant k such that T < kn for all sufficiently large n. Therefore O(n!^2) is not the the same as O(n!), but for example both 10n!, 10000n!, n! + n^2 (note the plus) are O(n!).

Another way to think about this: suppose you believe that O(n) and O(n^2) are distinct. Now plug in only numbers that are factorials (2, 6, 24, ...).