i wouldn't expect someone to know how to derive big-o bounds, I'm 45, an engineer at google and I couldn't do it if asked on the spot. I would however expect you to know of the basic asymptotic performance of typical data structures and algorithms. As a practical matter I've seen a number of critical bugs in software because of mistakes in choosing data structures.

As a side note, I joined Google at age 39.