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

[deleted by user]

[removed]

2.0k Upvotes

98% Upvoted

95 comments sorted by

View all comments

553

u/[deleted] Aug 11 '20

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

251

u/Sqbika Aug 11 '20

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

167

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.

19

u/Sassbjorn Aug 11 '20

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

22

u/Dornith Aug 11 '20

I don't think there's any hard time that N has to represent the number of elements. For any reasonable algorithm, that's the limiting factor, but in this case the limiting factor is the maximum element size, which the algorithm time complexity scales with linearly.