Re: O(n) Good Enough

James Jones <>
17 Jan 1999 20:46:02 -0500

          From comp.compilers

Related articles
O(n) Good Enough (Quinn Tyler Jackson) (1999-01-15)
Re: O(n) Good Enough (1999-01-17)
Re: O(n) Good Enough (James Jones) (1999-01-17)
Re: O(n) Good Enough (Glen Austin) (1999-01-17)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-19)
Re: O(n) Good Enough (David R Tribble) (1999-01-22)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-23)
| List of all articles for this month |

From: James Jones <>
Newsgroups: comp.compilers
Date: 17 Jan 1999 20:46:02 -0500
Organization: Microware Systems Corporation
References: 99-01-052
Keywords: parse

I can't speak for the second question, but something less than O(n)
wouldn't be looking at all the input, and it's hard to imagine being
able to always do that in a parser.


Quinn Tyler Jackson wrote:
> Two simple questions:
> Is a O(n) parser good enough?
> Although there is plenty of literature discussing the efficiency of
> low level (read character based) pattern matching algorithms, I
> haven't found much O(x) [where x is anything from n log m to n^r] type
> literature on the efficiency of parsers. Any pointers to literature
> in this area?

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.