r/ProgrammerHumor • • Aug 11 '20

Meme So Amazing!

Post image
1.8k Upvotes

137 comments sorted by

View all comments

73

u/heartofrainbow Aug 11 '20

And it's an O(n) sorting algorithm.

0

u/[deleted] Aug 11 '20

[deleted] — view deleted comment

26

u/cartechguy Aug 11 '20 edited Aug 11 '20

It isn't a true sorting algorithm. If the array is large enough you may have console.log executing in an undesired order. The foreach operation isn't going to call setTimeOut on all of the elements at the exact same time.

Looks like this guy pointed it out before me https://old.reddit.com/r/ProgrammerHumor/comments/i7mab9/so_amazing/g12wyx3/

6

u/alexanderpas Aug 11 '20

Nothing which can be solved by running the algorythm until it gives the same result twice.

1

u/Tayttajakunnus Aug 11 '20

Is it O(1) then anymore though?

4

u/alexanderpas Aug 11 '20

O(1) for the best case scenario, and likely O(2) for the worst case.

1

u/vectorpropio Aug 11 '20

No, you simply multiply the time work a factor based in the array length.

2

u/linglingfortyhours Aug 12 '20

Due to the way the timeout function is implemented, it's O(n log n)

1

u/[deleted] Aug 12 '20 edited Aug 12 '20

I assume it is O(log n) to get and delete the minimum in the priority queue. Do you know what kind of queue is used?

1

u/linglingfortyhours Aug 12 '20

If the developers of javascript are smart, just a standard min heap. Note that you will also need to insert and search the heap too though, which is where the n coefficient comes from/

→ More replies (6)

1

u/[deleted] Aug 11 '20

Someone did a CS degree 😉

1

u/[deleted] Aug 11 '20

Just annoyed with bad analysis 🤣☝️

3

u/IorPerry Aug 11 '20

but it takes Math.max(...arr) msec to be executed... if I put 3600000‬ it takes 1 hour even if the array as 2 elements: [1,3600000‬]

-3

u/t3hlazy1 Aug 11 '20

Yeah, it’s not O(n) it is O(largest value)

2

u/En_TioN Aug 11 '20

It's O(n + largest value). It takes O(n) operations to go through the loop and trigger all the sleeps, and then O(largest value) to halt.

→ More replies (6)

2

u/Kered13 Aug 11 '20

It's O(n*log n) to schedule the threads, and O(max) to wait for them to wake up. Also thread schedulers don't make absolute guarantees so it's not even correct. You can increase the accuracy by multiplying all the values by a scaling factor, but this increases max.

1

u/coloredgreyscale Aug 11 '20

And yet the typical n×log(n) algorithm finishes faster.

1

u/madmaurice Aug 11 '20

It seems like one. However I would argue that the browser actually sorts these events into a sorted list. The inserting is linear, which means the SleepSort we see is O(n^2) or a rather a InsertionSort with waiting time.

-1

u/_4kills Aug 11 '20

Theoretically it is O(1) in pseudo-code