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.
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, …).
You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !programmerhumor@lemmy.ml
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.
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.
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)
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, …).