Timeline for Algorithms for sorting under some restrictions
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2023 at 6:01 | history | edited | Varun Vejalla | CC BY-SA 4.0 |
added 67 characters in body
|
| Apr 22, 2023 at 6:00 | comment | added | Varun Vejalla | @YvesDaoust Yes you're right, I've added that in. | |
| Apr 20, 2023 at 6:37 | comment | added | user16034 | Your model does not account for the time to scroll the window. IMO this can be the dominant cost. | |
| Apr 19, 2023 at 23:01 | answer | added | D.W.♦ | timeline score: 1 | |
| Apr 19, 2023 at 21:54 | history | edited | Varun Vejalla | CC BY-SA 4.0 |
added 225 characters in body
|
| Apr 19, 2023 at 21:52 | comment | added | Varun Vejalla | @D.W. You're right, I'll make the edit for $O(\log n)$ bits of memory, instead of $O(1)$ - thanks for pointing that out. And mainly asymptotic running-time, although I am interested in the practical solutions too. | |
| Apr 19, 2023 at 20:43 | comment | added | D.W.♦ | Do you care about practical solutions, or asymptotic worst-case running time (i.e., theoretical complexity)? | |
| Apr 19, 2023 at 20:41 | comment | added | D.W.♦ | Constant additional space sounds like a severe restriction: you can't even remember an index into the array. Would you be satisfied with a solution that uses $O(\lg n)$ additional bits of memory, so that you can store a constant number of indices/pointers into the array? (How do you even implement something like insertion sort or selection sort without being able to store indices to the array?) | |
| S Apr 19, 2023 at 18:30 | review | First questions | |||
| Apr 27, 2023 at 3:12 | |||||
| S Apr 19, 2023 at 18:30 | history | asked | Varun Vejalla | CC BY-SA 4.0 |