My coworker and I have been puzzling over this problem.
(9:01:04 AM) Evan: ha
(9:01:28 AM) Evan: i thought of an insane way to do it
(9:01:32 AM) Dan: yeah???
(9:01:43 AM) Evan: i don’t think it’d be more efficient
(9:01:50 AM) Evan: in fact, i’m pretty sure it’d be less efficient
(9:02:24 AM) Dan: haha, ok, tell me anyway
(9:02:40 AM) Evan: it involves using an array of size n!
(9:02:46 AM) Dan: hahahahaha
(9:02:50 AM) Dan: well that right there
(9:02:56 AM) Dan: is nuts
(9:02:58 AM) Dan: but go on
(9:03:04 AM) Evan: oh f***
(9:03:05 AM) Evan: nevermind
(9:03:09 AM) Dan: ?!?
(9:04:08 AM) Dan: dude i like the notion that such a solution for a sequence of 10 operations would require an array with storage for over 3 million elements
(9:04:38 AM) Evan: hahahhahaha
(9:04:41 AM) Evan: yeah man nevermind
(9:04:58 AM) Evan: even that solution is actually 2*n!
Can you figure out a solution that beats O(N log N)?
*By “in the world,” I really just mean “between me and my friend Evan.”