I am going to blame my poor background in mathematics for my current confusion. Mainly it is the terminology that is highly confusing to me at the moment. That being said, I can fathom the sorting methods to an extent, but it is the notation and higher level mathematical thinking that is flying over my head.
I am making the vote for O(n) mainly because I do not understand how we could not check for duplicate characters without sorting them alphabetically first.
Hard to say as I don’t fully understand the process at the moment. Hopefully all will be clear in the future. : )