I'm not advocating for spot tests on complex algorithms without context. However, I believe a conversation about fundamental concepts like big-O notation reflects on one's approach to problem-solving and software design. It's not about dismissing anyone's experience or capability but ensuring a solid foundation that benefits all aspects of engineering work.
I understand senior engineers being out of practice and not being able to derive things like topological sort on the fly, but an inability to talk about the basics of big-O or the simplest of data structures is more commonly a red flag than "rust." If they never learned the material, that's a red flag. If they learned the material and they've been building software for the last decade without taking the basics of the material into account while coding, then that is a red flag as well.
Again, happy to admit that this is a flawed approach that will lose some great engineers, but most engineers that have your line of thinking are ones I actively avoid hiring. These concepts are practical, available to learn for free, and easy to understand. If an engineer feels that testing these concepts is beneath them, then they definitely aren't a good fit for any team I'm on. Big-O is to software engineers what Ohm's Law is to electricians. Imagine a world where electricians thought it was demeaning to talk about Ohm's law in an interview. ¯\_(ツ)_/¯