Timeline for Worst case lower bound of the general number guessing problem
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2022 at 22:37 | comment | added | D.W.♦ | Please credit the original source of all copied material: cs.stackexchange.com/help/referencing | |
| May 8, 2022 at 13:55 | history | edited | Metropola Official | CC BY-SA 4.0 |
edited title
|
| May 8, 2022 at 12:01 | comment | added | Yuval Filmus | The worst-case complexity is precisely $n$. Ask for the numbers $1,\ldots,n$. If $k$ is equal to one of them, you're done, and otherwise, $k = 0$. You can show that $n$ queries are necessary using an adversary argument: after $n-1$ questions answered negatively, there are still at least two possible values of $k$ which are consistent with everything known so far. | |
| May 8, 2022 at 11:31 | history | edited | Metropola Official | CC BY-SA 4.0 |
added 44 characters in body
|
| S May 8, 2022 at 11:23 | review | First questions | |||
| May 8, 2022 at 15:27 | |||||
| S May 8, 2022 at 11:23 | history | asked | Metropola Official | CC BY-SA 4.0 |