Timeline for Algorithm to find approximate position of element from a noisy sorted list
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 14, 2021 at 13:17 | comment | added | nehem | My mistake, I must have mentioned. The way nature of the problem(words sorted by frequency of use) it’s evident that more noise to be expected at the right end of the spectrum. | |
| Sep 14, 2021 at 9:22 | comment | added | Inuyasha Yagami | @nehem I did not understand. In the question, it is not mentioned that noise is increasing towards right. | |
| Sep 14, 2021 at 8:43 | history | edited | Inuyasha Yagami | CC BY-SA 4.0 |
added 24 characters in body
|
| Sep 14, 2021 at 7:55 | comment | added | nehem | Yeah, the noise will get bigger at the far right side of the array, meaning c will keep increasing when the boundary moves towards right. That roughly puts n^2 performance. | |
| Sep 14, 2021 at 7:52 | comment | added | Inuyasha Yagami | @nehem Right. There is a trade-off, choosing $c = 1$, will give you a less accurate result but converge fast. For larger $c$, it would be a more accurate result but it will converge slowly. As I said, it is simply a heuristic. You can even choose $c = 0 $, up to you. | |
| Sep 14, 2021 at 7:49 | comment | added | nehem | Well, then each comparison from m-c to m+c is considered one iteration(comparison), means it will take far longer to converge. | |
| Sep 14, 2021 at 7:06 | history | answered | Inuyasha Yagami | CC BY-SA 4.0 |