Timeline for The fastest way to find one unique value when all other values are the same
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 26, 2020 at 1:19 | history | edited | GZ0 | CC BY-SA 4.0 |
edited body
|
| Jul 26, 2020 at 0:00 | history | edited | GZ0 | CC BY-SA 4.0 |
deleted 8 characters in body
|
| Jul 25, 2020 at 22:39 | history | edited | GZ0 | CC BY-SA 4.0 |
added 210 characters in body
|
| Jul 25, 2020 at 21:40 | comment | added | Kelly Bundy | An improved version of your second solution is now by far the fastest :-) | |
| Jul 25, 2020 at 14:35 | comment | added | Peter Cordes | I was going to say "improves the average-case time complexity" should maybe just be "average-case time", but I guess we can say "complexity" and be more specific than "complexity class" (big-O or theta) where you drop all constant factors and smaller terms. I also wanted to point out that an early-out improves the best-case time to O(1), when the first 3 elements differ. (Or with SIMD, if the first 4 elements aren't all equal, then you only have to look at 1 vector.) Also +1 for the Python specific ways of reducing interpreter overhead, which is massive for CPython. | |
| Jul 25, 2020 at 8:47 | history | edited | GZ0 | CC BY-SA 4.0 |
edited body
|
| Jul 25, 2020 at 8:06 | history | edited | GZ0 | CC BY-SA 4.0 |
added 60 characters in body
|
| Jul 25, 2020 at 7:47 | history | edited | GZ0 | CC BY-SA 4.0 |
added 15 characters in body
|
| Jul 25, 2020 at 7:47 | comment | added | GZ0 | @tinstaafl O(n-1) is the same as O(n). If an algorithm is O(n), it means the runtime is upper-bounded by a linear function of the input size n when n is sufficiently large. Actual runtimes of both 2n and 0.01n are both O(n). I have edited my answer to be more accurate. | |
| Jul 25, 2020 at 7:41 | history | edited | GZ0 | CC BY-SA 4.0 |
added 8 characters in body
|
| Jul 25, 2020 at 7:14 | comment | added | user33306 | How about O(n-1)? That's better than O(n). | |
| Jul 25, 2020 at 6:55 | history | edited | GZ0 | CC BY-SA 4.0 |
added 103 characters in body
|
| Jul 25, 2020 at 6:48 | history | edited | GZ0 | CC BY-SA 4.0 |
added 103 characters in body
|
| Jul 25, 2020 at 6:35 | history | edited | GZ0 | CC BY-SA 4.0 |
added 103 characters in body
|
| Jul 25, 2020 at 6:25 | history | answered | GZ0 | CC BY-SA 4.0 |