Paper: On The Mathematical Properties Of Linguistic Theories

ACL ID P83-1015
Title On The Mathematical Properties Of Linguistic Theories
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1983

This is the purpose of O-no~.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 '.verst-case time complexity ts O(g) if the worst-ease 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 worst-case complexity can b...