• remi_pan@sh.itjust.works
    link
    fedilink
    arrow-up
    4
    ·
    4 months ago

    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
      link
      fedilink
      arrow-up
      6
      arrow-down
      3
      ·
      4 months ago

      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
        link
        fedilink
        arrow-up
        7
        ·
        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, …).