I’m going to say O(n).
With a radix sort you get O(k + n) and you could additionally save time on the compare step as once you come across a letter with a non-empty “bucket”, you’ve proven the result to be false.
I’m going to say O(n).
With a radix sort you get O(k + n) and you could additionally save time on the compare step as once you come across a letter with a non-empty “bucket”, you’ve proven the result to be false.