4 ms·
Given that my socks are partitioned into two sets (washing basket and drawer) and as I mentioned above I would throw them out if the failure rate became high en
by VBprogrammer 15y ago
Given that my socks are partitioned into two sets (washing basket and drawer) and as I mentioned above I would throw them out if the failure rate became high enough to impact the asymptotic behavior I'd say that O(1) is probably correct.
- mathattack 15y agoIf a sock has a hole, it gets tossed. Now that I think of it, the mixed sock problem can actually be worse than O(n^2). For instance, if I decide that I want to wear my Marvin the Martian socks, and can only find one in the sock drawer, then it's a big problem. Look in the other drawers. Look under the bed. Look in the dryer. Repeat. Repeat. Until the other one is given up for lost.
- farnsworth 15y agoIt doesn't depend just on n since you aren't just searching through n available socks, you are searching k places with n_k socks in each place and with p_k confidence that you have thoroughly searched each place. I can't think of a more general problem that this might correspond to.
- mathattack 15y agoWill it get solved when we straighten out this whole P NP business?