This is weird - do big companies actually ask stupid questions I can google, and let non-technical people lecture engineers on Big-O?
Hope this obviously talented person finds more meaningful employment elsewhere.
replies(1):
Well, he was interviewing _for_ google. Maybe they wrote up the test before google was online and forgot to update it.