Timeline for Find the maximum of ax+b
Current License: CC BY-SA 4.0
36 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 14, 2018 at 7:12 | history | edited | jimmy23013 | CC BY-SA 4.0 |
Well I don't understand what I meant in the last paragraph, so changed it as an attempt to make it clear
|
| Aug 7, 2015 at 15:13 | history | edited | Peter Taylor |
edited tags
|
|
| May 2, 2015 at 15:55 | history | tweeted | twitter.com/#!/StackCodeGolf/status/594530536133124097 | ||
| Mar 16, 2015 at 3:03 | review | Close votes | |||
| Mar 16, 2015 at 10:50 | |||||
| Mar 14, 2015 at 4:39 | history | edited | jimmy23013 |
edited tags
|
|
| Mar 13, 2015 at 9:03 | vote | accept | jimmy23013 | ||
| Mar 9, 2015 at 3:54 | answer | added | Maltysen | timeline score: 1 | |
| Mar 8, 2015 at 22:12 | answer | added | Keith Randall | timeline score: 10 | |
| Mar 8, 2015 at 21:50 | history | edited | jimmy23013 | CC BY-SA 3.0 |
added 38 characters in body
|
| Mar 8, 2015 at 21:21 | history | edited | jimmy23013 | CC BY-SA 3.0 |
added 35 characters in body
|
| Mar 8, 2015 at 21:15 | comment | added | jimmy23013 | @KeithRandall Rollbacked the edit... | |
| Mar 8, 2015 at 21:14 | history | rollback | jimmy23013 |
Rollback to Revision 4
|
|
| Mar 8, 2015 at 21:13 | comment | added | Keith Randall | You want expected complexity. Expected over the random choices of the algorithm, not over any input distribution. | |
| Mar 8, 2015 at 21:08 | comment | added | jimmy23013 | Well, seeing the history, that line is just edited to the Wikipedia page recently. Edited and tried to not mention that. And I'm a bit confused... | |
| Mar 8, 2015 at 21:06 | history | edited | jimmy23013 | CC BY-SA 3.0 |
added 108 characters in body
|
| Mar 8, 2015 at 20:53 | comment | added | jimmy23013 | @flawr What I get from this page is that "average-case complexity" is usually for the average input, and "expected complexity" is for the randomness. If I misstood that, I'm not sure what term to use then. | |
| Mar 8, 2015 at 20:43 | comment | added | flawr |
@user23013 Then please change that in the question, because you wrote the expected complexity should be O(n log(n)) =)
|
|
| Mar 8, 2015 at 20:41 | comment | added | jimmy23013 | @flawr It's basically just the worst-case complexity allowing the randomized quicksort (and things likely). | |
| Mar 8, 2015 at 20:35 | comment | added | flawr | @user23013 The asympotic runtime of many algorithms depends on assumptions on the input distributions, thats why I am asking. | |
| Mar 8, 2015 at 20:27 | comment | added | jimmy23013 | @KeithRandall No. | |
| Mar 8, 2015 at 20:27 | comment | added | Keith Randall | Can we assume that X is sorted on input? | |
| Mar 8, 2015 at 20:13 | review | Close votes | |||
| Mar 8, 2015 at 23:03 | |||||
| Mar 8, 2015 at 20:13 | comment | added | jimmy23013 | @flawr You can assume each number is in a basic integer type. The "expected complexity" is for the randomness in your program, and it cannot depend on the input distribution. | |
| Mar 8, 2015 at 20:07 | comment | added | jimmy23013 | @flawr Find the part of the convex hull of the points (a,b), from the topmost to rightmost point, and do binary search on the slope (or find the maximum for unimodal function) for each x. | |
| Mar 8, 2015 at 19:56 | comment | added | flawr | And how do we have to expect the numbers to be distributed? | |
| Mar 8, 2015 at 19:43 | comment | added | flawr |
Why is it clear that it is even possible in O(n log(n))? Can you provide a reference algorithm?
|
|
| Mar 8, 2015 at 17:10 | answer | added | coredump | timeline score: 2 | |
| Mar 8, 2015 at 12:20 | history | edited | jimmy23013 | CC BY-SA 3.0 |
added 47 characters in body
|
| Mar 8, 2015 at 6:50 | comment | added | jimmy23013 | @Optimizer Right. | |
| Mar 8, 2015 at 6:39 | comment | added | Optimizer | total input length = length of (a,b) pairs plus length of array of x ? | |
| Mar 8, 2015 at 6:15 | answer | added | Matt Noonan | timeline score: 6 | |
| Mar 8, 2015 at 0:29 | history | edited | jimmy23013 | CC BY-SA 3.0 |
edited body
|
| Mar 8, 2015 at 0:17 | comment | added | jimmy23013 | @BobJarvis It's the maximum of ax+b for the corresponding x, but for all (a,b) in the list. Changed to make the example less misleading. | |
| Mar 8, 2015 at 0:15 | history | edited | jimmy23013 | CC BY-SA 3.0 |
added 6 characters in body
|
| Mar 8, 2015 at 0:14 | comment | added | Bob Jarvis - Слава Україні | It looks to me like the expected results should be [11 12 12 15 4]. ??? | |
| Mar 7, 2015 at 23:29 | history | asked | jimmy23013 | CC BY-SA 3.0 |