ListBox.FindString what's the worst case runtime? O(n), O(n log n), O(1)?

Question

Out of curiosity, what is ListBox.FindString(string)'s worst case runtime? MSDN does not state this in its API docs.

I have a strong suspicion it is O(n), I have a sorted list and O(log n) or O(1) would be nice, is there a way to change which sorting algorithm FindString uses at runtime?

Answer 1

If you have enough strings in the ListBox such that the big O of how FindString() works matters, you need to look at another way of storing your strings.

Answer 2

"Finds the first item in the ListBox that starts with the specified string."

That smells like a linear search from the start of the list, but there's no way to know for sure.

You can't change what algorithm ListBox uses, but you can extend ListBox and have your extended class do whatever you wish. :D

Answer 3

Regardless of whether its a good idea to have a huge number of items in a listbox to the point where it would matter (It might be cumbersome for the user, depending on your implementation.), I'm going to guess O(n) since I believe it does a partial match that is case insensitive.

Answer 4

Actually, you can see what the method does, as Microsoft make their .net base class source code available via 'Microsoft Reference Source Code' (clicky) - you can step into BCL code in VS (also much of the BCL stuff is available via Rotor, the open source implementation of .net, however WinForms code is not available IIRC).

Examining the code (which I don't want to paste here just in case it violates MS's license), it's clear the method is O(n) worst-case.

Basically the method loops through each item in the list, moving back to the top of the list if the bottom is reached (through a crafty use of the ever-lovely mod (%) operator and a counter). Obviously that is O(n) in the worst-case (i.e. the searched-for item is not in the list) where it would have to iterate over every member of the list.