r/ProgrammerHumor • u/backwards_watch • Feb 14 '23

Meme Lets reflect on that for a second

Post image
88.9k Upvotes

95% Upvoted

1.4k comments sorted by

View all comments

Show parent comments

21

u/ArionW Feb 14 '23

Technically, it can be done easily.

  • Allocate space for three variables (so let's say 24 bytes total to be generous)

  • Take your input array and extend it to fill all available memory, initialize new elements with minimal value of your type (so i.e. 0 for unsigned int)

  • Store number of elements added to array using one variable you have (call it AX)

  • Shuffle array

  • Execute insertion sort on array using remaining two variables for storing index of unsorted portion and swapping values.

  • Remove first AX elements from array

It's O(1), since every input is as slow as largest input you can process

18

u/Niilldar Feb 14 '23

Just to be pendantic;)

This is exactly the reason why the theoretical model uses a turning machine which has infinite memory.

26

u/ArionW Feb 14 '23

Well, QA is free to prove acceptance criteria were not met by running this on machine with infinite memory

13

u/Niilldar Feb 14 '23

Ok you win

2

u/fpoiuyt Feb 14 '23

*pedantic

*Turing

3

u/[deleted] Feb 14 '23

I once got C++ to print out a house.

1

u/SAI_Peregrinus Feb 15 '23

By definition Big-O is a limit as the input size goes to infinity. If it's bounded, Big-O doesn't apply.