Timeline for How to find 5 repeated values in O(n) time?
Current License: CC BY-SA 3.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2017 at 4:55 | vote | accept | darylnak | ||
| Oct 10, 2017 at 10:06 | comment | added | Alex Reinking | I guess that works, but that's not what "repeat" typically means in such a context. Think of the string "repeat" function in many languages' standard libraries. "abc".repeat(1) would not be expected to double the string. | |
| Oct 10, 2017 at 10:01 | comment | added | LangeHaare | @AlexReinking I think you have to interpret a "repeat" as a value that has already appeared earlier in the array. E.g. with n=7 you can have [1,1,1,1,1,2,2] - 1 "appears" once and then "repeats" four times, 2 "appears" once and then "repeats" once | |
| Oct 10, 2017 at 9:55 | answer | added | someone12321 | timeline score: 0 | |
| Oct 10, 2017 at 4:39 | answer | added | user78484 | timeline score: -2 | |
| Oct 9, 2017 at 19:29 | answer | added | Veedrac | timeline score: 3 | |
| S Oct 9, 2017 at 17:42 | history | suggested | Ilmari Karonen | CC BY-SA 3.0 |
finding just one repeated value is quite a bit simpler
|
| Oct 9, 2017 at 17:11 | review | Suggested edits | |||
| S Oct 9, 2017 at 17:42 | |||||
| Oct 9, 2017 at 11:55 | review | Suggested edits | |||
| Oct 9, 2017 at 14:42 | |||||
| Oct 9, 2017 at 11:05 | comment | added | Alex Reinking | For $n=6$, the only allowable number is $1$, by your description. But then $1$ would have to be repeated six, not five, times. | |
| Oct 9, 2017 at 0:33 | answer | added | Veedrac | timeline score: 8 | |
| Oct 8, 2017 at 22:57 | answer | added | Hauleth | timeline score: 0 | |
| Oct 8, 2017 at 21:16 | comment | added | leftaroundabout | @RomanGräf it appears the actual situation is this: the algorithms work in $O(\log k \cdot n)$, where $k$ is the size of the domain. So, for a problem like the OP's, it comes down to the same whether you use such an algorithm on the $n$-sized domain, or a traditional $O(n\cdot \log n)$ algorithm on an unbounded-size domain. Makes sense, too. | |
| Oct 8, 2017 at 20:49 | comment | added | leftaroundabout | @RomanGräf I don't actually know how these algorithms work, and in fact I was always suspicious about the caveats with “pre-allocated array with constant overhead”. Some testing of implementations suggests they definitely do better than $O(n^2)$ time though (1e5 -> 0.138s, 1e6 -> 1.434s, 1e7 -> 16.104s). In each case, it's still much slower than an optimised $O(n\cdot\log(n))$ algorithm on the same machine, but the scaling seems to be as advertised. | |
| Oct 8, 2017 at 19:32 | comment | added | Linnea Gräf | @leftaroundabout These algorithms are $O(k\cdot n)$ where $n$ is size of the array and $k$ is the size of the input set. since $k=n-constant$ these algorithms work in $O(n^2)$ | |
| Oct 8, 2017 at 19:13 | answer | added | einpoklum | timeline score: 1 | |
| Oct 8, 2017 at 17:34 | comment | added | leftaroundabout | Sorting integers is $O(n)$. | |
| Oct 8, 2017 at 16:37 | comment | added | anon | $O(n \log n) + O(n)$ is not $O(n^2 \log n)$. It's $O(n \log n)$. It'd be $O(n^2 \log n)$ if you did the sort n times. | |
| Oct 8, 2017 at 14:52 | history | tweeted | twitter.com/StackCompSci/status/917039926021156865 | ||
| Oct 8, 2017 at 13:29 | answer | added | Stella Biderman | timeline score: 5 | |
| Oct 8, 2017 at 13:07 | history | edited | Raphael |
edited tags
|
|
| Oct 8, 2017 at 11:53 | answer | added | Yuval Filmus | timeline score: 25 | |
| Oct 8, 2017 at 11:45 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 18 characters in body
|
| Oct 8, 2017 at 11:37 | history | edited | fade2black | CC BY-SA 3.0 |
added 21 characters in body
|
| Oct 8, 2017 at 11:35 | answer | added | fade2black | timeline score: 22 | |
| Oct 8, 2017 at 11:28 | review | First posts | |||
| Oct 8, 2017 at 11:53 | |||||
| Oct 8, 2017 at 11:26 | history | asked | darylnak | CC BY-SA 3.0 |