I had thought the solution was very simple before you pointed this out. With some difficulty I improved my solution to O(log(log(n)) * log(n)), and it took quite a bit more time for me to get completely constant sized stack frames.

I suspect most people initially come up with the O(log^2(n)) solution and jump next to the O(log(n)) solution without getting stuck in the middle there, but I'm curious if this gave you any problems.