I don't like this question. Comparison- or value-based? Worst in the average or the best case? What's to stop me from mapping the inputs into, say, busy beaver space?
In an actual interview situation, I'd be likely to just choke, because it's a question I can't get a good handle on. I hope you prod & probe when asking that question.