I expected him to know quite a bit about the language itself, but the discussion did not get past the point where I asked about the number of operations needed to find an element in a sorted array of length N.
So he doesn't know about compilers and the C++ language because he didn't know about computational complexity or at least Big O notation? You should have asked about language features and syntax, inheritance or something if you wanted to determine if he really wrote a C++ compiler.
It's similar to you saying you built a piano and I ask you to play some Chopin or Bach for me. But you never claimed to know how play it, you just built in. If I wanted to know about your ability to build pianos I should ask questions about the construction and internal workings of it.
His skills may not be what you're looking for, and that's fine, but to consider him incompetent seems too far a stretch.