CODEWITHSUNDEEP
c++stringperformancesearchtime-complexity
Saif
Saif

Reputation: 1905

Finding character in a string in less than O(n)

Is it possible to search a character in a string in less than O(n). Most of the algorithms I have come across takes O(n) time. string::find() takes O(N*M). Is there any algorithm in which you are not required to traverse the whole string.

Upvotes: 0

Views: 373

Answers (1)

Leolian
Leolian

Reputation: 201

Well first I must say there isn't algorithm less than linear O(n) time complexity for your problem.

Of course you can try randomized algorithm like Las Vegas way of thinking. Pick a random spot from your array if lucky you found your char if not try again and store the wrong index.

Worst case is like linear search O(n) but purely lucky if you get it in few first tries it's way less. This kind of algorithm maybe is what you are looking for. On average it will find char maybe faster but remember if it still takes k tries when for sure k < n it is still linear time. O(k)

If you know more from your input maybe you can think of way to solve it differently.

Hope this helps

Upvotes: 2

Related Questions