The purpose of mentioning the Big-O in that document wasn't to inform about what it is. Rather, it was to note to the candidate not to go into technical detail during the interview (i.e. we like the intuitive version).