Steve Jobs Book Excerpt: Why he wore the black mock turtleneck uniform

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by kylewpppd on Tuesday October 11, 2011 @06:49PM (#3100741)

So I would argue that the matching problem with many different styles of socks is O(n^2), since we first must select one sock appropriate for the occasion, then rummage through all the other socks to select its match. This does have the problem that your algorithm may never finish if your laundry eats socks like mine does.

And that with all identical pairs, I assert the solution is O(n), since there is a chance that you will have to iterate through all of your socks to find one with no holes/is clean. However, I think the latter case is Omega(1). Not quite so sure about the first one.

[ Parent | on HN ]

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by kragen on Wednesday October 12, 2011 @12:34AM (#3101521)

Previous discussion of this question:

http://www.mail-archive.com/[email protected]/msg0008...

http://news.ycombinator.com/item?id=1696125

[ Parent | on HN ]

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by stralep on Tuesday October 11, 2011 @08:44PM (#3101029)

If ordering is made by color&design, matching drops to O(n log(n)).

Again, with ordering, searching drops to O(log n)

[ Parent | on HN ]

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by sid0 on Wednesday October 12, 2011 @12:56AM (#3101561)

However, that actually requires ordering socks, which as we all know is O(not gonna happen).

[ Parent | on HN ]

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by VBprogrammer on Tuesday October 11, 2011 @07:04PM (#3100802)

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.

[ Parent | on HN ]

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by mathattack on Tuesday October 11, 2011 @07:17PM (#3100837)

If 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.

[ Parent | on HN ]

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by farnsworth on Tuesday October 11, 2011 @08:11PM (#3100983)

It 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.

[ Parent | on HN ]

Re:Steve Jobs Book Excerpt: Why he wore the black mock turtl... by mathattack on Tuesday October 11, 2011 @09:01PM (#3101048)

Will it get solved when we straighten out this whole P NP business?

[ Parent | on HN ]