ACL Anthology Network (All About NLP) (beta) The Association Of Computational Linguistics Anthology Network 
ACL ID  P831015 

Title  On The Mathematical Properties Of Linguistic Theories 
Venue  Annual Meeting of the Association of Computational Linguistics 
Session  Main Conference 
Year  1983 
Authors 

This is the purpose of Ono~.Oon. Let f(n) and g(n) be two ~ui%cttons. ], ts said to be O(g),.f a constant multiple of ~ is an upper bound for f, ~or ~tl[ but a finite number o~ values of n..~[ore precisely, f ts O(g) ff ~here,s are constants K and n O such that ~or all ~%>~e ],(n) < K'y('.'~). Given an algorithn~. M, we will say that tts '.verstcase time complexity ts O(g) if the worstease time cost function cw(.n ) :or M is O(g) Notice that this merely says that almost all ~nputs to M of s,ze n can be processed in time at most a constant times g(n). It does nat ~ay that alJ Lnputs requLre g[~%) time, or even that any do even on M, let alone on any other machine that Lmp[ements ],. Also, if two algorithms A] and A 2 are avaHab[e for a function]'. and [[ their worstcase complexity can b...