Running time of string.Split method

Question

Following the responses to this, I am curious to know what is the running time of String.Split()

string source = "source string;this,"; //length n
string[] splitted = source.Split(' ',',',';'); //delimiter array of length m

Is it O(m*n) ?

Answer 1

According to this thread, it's O(N):

Internally, it uses a 2 pass routine. In the first pass, the index of the separator characters are discovered and stored. In the second pass, the string is "split" by calling Substring repeatedly and storing the results in an output array using the indices previously saved.

As such, the algorithm is effectively O(N), since it's doing linear passes through the input string.

Note: it seems that author of the statement above is SO user - maybe he can help with more detailed answer.

If you want to check the sources yourself, download tool such as ILSpy, reference mscorlib and search for Split implementation.