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) ?
Asked
Active
Viewed 1.1k times
9
-
You could benchmark this. I certainly cannot find documentation for the complexity. – erisco Jan 30 '12 at 17:30
-
1Why not open up the source and take a look? – N_A Jan 30 '12 at 17:33
-
http://msdn.microsoft.com/en-us/library/b873y76a.aspx – Massimiliano Peluso Jan 30 '12 at 17:34
-
@mydogisbox Where can I find it. – Nemo Jan 30 '12 at 17:34
-
@MassimilianoPeluso Running time is not there in the page. – Nemo Jan 30 '12 at 17:34
-
you have to run your benchmark as it is not even on MSDN – Massimiliano Peluso Jan 30 '12 at 17:37
-
http://referencesource.microsoft.com/netframework.aspx – N_A Jan 30 '12 at 17:37
1 Answers
7
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.
-
1https://social.msdn.microsoft.com/Forums/vstudio/en-US/90d6eeed-b7a3-494a-8c90-5035f8465622/algorithm-behind-stringsplit-method?forum=netfxbcl – Manu Mohan Jun 23 '16 at 09:02