cc @jliszka
-
-
-
Expectation is linear, so it's the sum from i = 1 to n of the expected number of boxes you need to open to get something you don't already have given that you have i things already. def f(n: Int) = (1 to n).map(i => 1.0 * n / i).sum Seems to check out experimentally too
- Show replies
New conversation -
-
-
First one is the “coupon collector problem”. So NlogN.
- End of conversation
New conversation -
-
-
This Tweet is unavailable.
-
This Tweet is unavailable.
- Show replies
-
-
-
Ah so “efficiently trading” is just collecting M copies of each? My hunch is MN + logN in that case but will have to think more. Intuitively when you still need to collect many copies of each toy each new purchase is useful. Things are harder when M is small
-
I meant MN + NlogN
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.