News for hackers. Stuff that matters.
Re:The "C is Efficient" Language Fallacy (2006) by chengl on Monday January 09, 2012 @11:55AM (#3443190)
What the author mentioned is longest common SUBSEQUENCE (not substring). And it's true that LCS requires O(n^2) if only need to find ONE LCS, using dynamic programming. But if it's required to find ALL longest common subsequence, it definitely requires higher order. http://en.wikipedia.org/wiki/Longest_common_subsequence_prob...

I agree that the author should post the code he used to benchmark different languages. Otherwise, it's not convincing

Re:The "C is Efficient" Language Fallacy (2006) by attractivechaos on Monday January 09, 2012 @01:24PM (#3443616)
Can you find the proof that finding all LCS is O(n^3)? The author was talking about "the standard algorithm for computing LCS". I was assuming the standard algorithm finds one LCS only.
Re:The "C is Efficient" Language Fallacy (2006) by cperciva on Monday January 09, 2012 @02:07PM (#3443782)
Indeed, finding all LCSs requires exponential time: The strings "abcdefghijkl..." and "badcfehgjilk..." have the 2^(N/2) LCSs "[ab][cd][ef][gh][ij][kl]..." and no algorithm can ever run faster than the amount of time it takes to print its output.