Timeline for Is this a correct approch of finding expected runtime of an algorithm?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 13, 2017 at 13:27 | vote | accept | ElleryL | ||
| Aug 13, 2017 at 12:51 | comment | added | Yuval Filmus | Your description is accurate. I recommend checking out the average time analysis of Quicksort. | |
| Aug 13, 2017 at 5:43 | comment | added | ElleryL | thanks so much, this is very helpful; so every time when I'm dealing with expected runtime; I consider the sample space as the set of all possible input. Based on the input, I calculate the runtime for each one; then there will be a distribution over all possible inputs; finally, I use expectation function; is there anymore similar type of questions that can get me to practice ? | |
| Aug 13, 2017 at 3:13 | history | answered | Yuval Filmus | CC BY-SA 3.0 |