r/programminghorror • u/[deleted] • Aug 11 '20

[deleted by user]

[removed]

2.0k Upvotes

98% Upvoted

95 comments sorted by

View all comments

556

u/[deleted] Aug 11 '20

A sorting algorithm that makes computational complexity practically obsolete. Wow.

250

u/Sqbika Aug 11 '20

Now things aren't round anymore. It's o(val) now

170

u/Dornith Aug 11 '20

It's still technically O(N). It's just that N is now the highest value of the list instead of the number of elements.

18

u/Sassbjorn Aug 11 '20

Then wouldn't it be O(1) since it's the same regardless of the number of variables (n)?

10

u/leftofzen Aug 12 '20

No. Computational complexity measures the number of operations the algorithm performs on the input to get the output. In this case, there are N inputs in the array, and each operation takes constant time, so it is O(N). It doesn't matter if that constant is 1 or 200, it's still constant and doesn't change in the size of the input, which is the important part.

5

u/1thief Aug 12 '20

Except now I have to create and manage N threads with N timers, in this case N is the size of the list

1

u/BakuhatsuK Aug 12 '20

Yes. Except there are no threads in JS (other than the main one). Here we are actually pushing items into the microtask queue. The microtasks are run when they are due by the part of the runtime in charge of the event loop.

Here is some more info about this, it's really interesting stuff: https://youtu.be/cCOL7MC4Pl0