Being familiar with big O notation is not that same thing as being familiar with a few basic complexity classes. I wouldn't be surprised or disappointed if a self-taught programmer was intimidated by big O notation, but I would be surprised if they were unfamiliar with the concept that hash map lookups are much faster than array searches, or that searching a sorted array is much faster than an unsorted array. You seem to be using "big O notation" to refer to fundamental competency about basic data structures. It's even quite possible and understandable for a self-taught programmer to, over time, figure out that certain big O classes refer to certain algorithms while still not understanding the meaning of the mathematical notation.