asdginioubnou

>Let's say there are M different characters in the alphabet and N different characters in the string.

I mean "N characters in the string", i.e. the string is length N. There won't be N different characters.

That doesn't make a difference asymptotically, though it obviously makes a big difference in practice.

The second solution is safer than the first. While it will sometimes be slower, it will never be catastrophically bad. It may have a small, predictable overhead, but it will never unexpectedly bring down the whole program when you get a few unusually long strings.

When searching through a sorted list, your first instinct should be to use binary search. Your first instinct should not be "well maybe the list is always small, so linear search would be faster." Write the safe, predictable thing and save the optimizations for later.

Both solutions are O(1). The alphabet is finite. Let's say there are M different characters in the alphabet and N different characters in the string. If there is a duplicate, it is guaranteed to occur within the first M + 1 characters of the string by the pigeonhole principle. As N grows without bound, the number of characters that needs to be checked reaches a limit.

(I guess, most precisely, we should define K to be min(M + 1, N). Then the first solution is O(K^2) and the second solution is O(K))

EDIT: I assumed the first solution would compare each character to the characters visited so far, i.e.

    for i in [0..N]
        for j in [0..i]
           if arr[i] == arr[j] return arr[i]

Maybe it's

    for i in [0..N]
        for j in [0..N]
           if arr[i] == arr[j] && i != j
               return arr[i]

That would make it O(KN). Or O(N) if we treat the size of the alphabet as fixed.

It's definitely wrong. A lot of people use "order of magnitude" to just mean "a lot".

I always use the precise meaning. It might be better for me to say "factor of ten" rather than "order of magnitude" if other people don't always use the precise meaning.