This morning in the shower, I finally solved an Algorithms-related problem that has had Reid and me stumped for a week (no, this is for fun; far too hard to be asked on a homework set):
Find positive, C-infinity, monotonically increasing functions f(n) and g(n) such that
f(n) is not in O(g(n)) and
g(n) is not in O(f(n)),
or
Show that no such functions exist.
Note that C-infinity means that not only is the function continuous, but its derivative is continuous, and the derivative of that is continuous, ad infinitum.
Can anyone else find an answer (hopefully simpler than mine)? It’s cheating if you look at Reid’s door.