• yetAnotherUser@feddit.de
    link
    fedilink
    arrow-up
    5
    ·
    1 year ago

    Thay depends on the size of the pile, there could be a lot of weight and instability above the pants and you’ll have to pull them out à la Jenga or carefully rearrange the stack.

    Since the amount of rearranging increases for larger n (imagine a pile reaching the ceiling), searching is in ω(1).

    • rasensprenger@feddit.de
      link
      fedilink
      arrow-up
      6
      ·
      1 year ago

      As the volume of the room is finite, even “exponential” or worse search algorithms will complete in constant time.

      • yetAnotherUser@feddit.de
        link
        fedilink
        arrow-up
        3
        ·
        1 year ago

        <.<

        Well, there’s only finitely many atoms in the universe, do all algorithms therefore have constant time?

        Although you could argue for very large amounts of clothes my method of throwing clothes on the floor starts performing worse due to clothes falling on the same spot and piling up again.

        Unless you extend your room. Let’s take a look at the ✨amortized✨time complexity.

        • rasensprenger@feddit.de
          link
          fedilink
          arrow-up
          4
          ·
          1 year ago

          Well landau notation only describes the behaviour as an input value tends to infinty, so yes, every real machine with constant finite memory will complete everything in constant time or loop forever, as it can only be in a finite amount of states.

          Luckily, even if our computation models (RAM/TM/…) assume infinite memory, for most algorithms the asymptotic behaviour is describing small-case behaviour quite well.

          But not always, e.g. InsertionSort is an O(n^2) algorithm, but IRL much faster than O(n log n) QuickSort/MergeSort, for n up to 7 or so. This is why in actual programs hybrid algorithms are used.