4 ms·

The package's original implementation[1] also seems like it would have resulted in O(n^2) operation rather than desired O(n). [1] https://en.wikipedia.org/wiki

The package's original implementation[1] also seems like it would have resulted in O(n^2) operation rather than desired O(n). [1] https://en.wikipedia.org/wiki/Npm_left-pad_incident https://en.wikipedia.org/wiki/Npm_left-pad_incident

hhjinks 1y ago
I don't see where the quadratic time complexity comes from. There's a single loop performing n operations in total, ie. O(n).
- barbegal 1y ago
  In each loop prepending a single character could take O(m) (moving all m characters one to the right) so combined O(nm) where n is the number of padding characters and m is the total number of characters in the string.
  - lifthrasiir 1y ago
    Only when the underlying JS implementation does this naively. In reality JS implementations do a lot of optimizations which often can reduce the time complexity.
    - bondarchuk 1y ago
      "The compiler will take care of it", funny, heard that one before, I'd profile it just to be on the safe side...
      - lifthrasiir 1y ago
        I didn't mean that. JS doesn't have any lower-level interface for handling memory, so such optimization has to be in the implementation. It should be quite obvious that relying on such optimization can be problematic.
- arcastroe 1y ago
  The line `str = ch + str` is itself a linear-time operation, with time proportional to the length of the new string. That linear-time operation is then additionally repeated `len` times
- deleted 1y ago
  [deleted]
- pbiggar 1y ago
  Extending strings is not a linear-time operation. Behind the scenes, the JS runtime allocates new memory for it. In the naive case, you start by allocating 1 byte, then when you append to it, you need 2 bytes. So you allocate a new string of 2 bytes, and copy the data in. Each new byte is a new allocation, and a new copy of the entire string. That's how it's quadratic. In practice, memory allocators tend to double the size of an allocation like this, which is still quadratic. In practice, JS runtimes also tend to use data structures like Ropes for strings to handle this sort of issue. That brings it down to linear time in practice (I think?)

hhjinks 1y ago

I don't see where the quadratic time complexity comes from. There's a single loop performing n operations in total, ie. O(n).

barbegal 1y ago
In each loop prepending a single character could take O(m) (moving all m characters one to the right) so combined O(nm) where n is the number of padding characters and m is the total number of characters in the string.
- lifthrasiir 1y ago
  Only when the underlying JS implementation does this naively. In reality JS implementations do a lot of optimizations which often can reduce the time complexity.
  - bondarchuk 1y ago
    "The compiler will take care of it", funny, heard that one before, I'd profile it just to be on the safe side...
    - lifthrasiir 1y ago
      I didn't mean that. JS doesn't have any lower-level interface for handling memory, so such optimization has to be in the implementation. It should be quite obvious that relying on such optimization can be problematic.
arcastroe 1y ago
The line `str = ch + str` is itself a linear-time operation, with time proportional to the length of the new string. That linear-time operation is then additionally repeated `len` times
deleted 1y ago
[deleted]
pbiggar 1y ago
Extending strings is not a linear-time operation. Behind the scenes, the JS runtime allocates new memory for it. In the naive case, you start by allocating 1 byte, then when you append to it, you need 2 bytes. So you allocate a new string of 2 bytes, and copy the data in. Each new byte is a new allocation, and a new copy of the entire string. That's how it's quadratic. In practice, memory allocators tend to double the size of an allocation like this, which is still quadratic. In practice, JS runtimes also tend to use data structures like Ropes for strings to handle this sort of issue. That brings it down to linear time in practice (I think?)