My Vote for O - Somewhere between nlogn & n

Unreal Courses Talk
,
#1

Without looking at anyone else’s answer:

My reasoning is that if the best sorting thing is nlogn, then it seems fairly trivial (heh) to cut the sort short if you find a copy.

This presumably won’t be O(n), but will be shorter than O(nlogn) - I guess probability will have something to say about the Order of this?
Maybe?

#2

Ahh, ok - so I admit to be influenced by other answers here:
Thinking about how to cut the search short, it does seem obvious to keep some kind of track of letters already used, which is basically how most people are settling on O(n)

So, can I change my vote please :smiley:

Privacy & Terms