Lower-bound Time-complexity Analysis of Logic Programs
Andy King, Kish Shen, Florence Benoy · The MIT Press eBooks · 1997
The paper proposes a technique for inferring conditions on goals that, when satisfied, ensure that a goal is sufficiently coarse-grained to warrant parallel evaluation. The method is powerful enough to reason about divide-and-conquerprograms, and in the case of quicksort, for instance, can infer that a quicksort goal has a time complexity that exceeds 64 resolution steps (a threshold for spawning) if the input list is of length 10 or more. This gives a simple run-time tactic for controlling spawning. The method has been proved correct, can be implemented straightforwardly, has been demonstrated to be useful on a parallel machine, and, in contrast with much of the previous work on time-complexity analysis of logic programs, does not require any complicated difference equation solving machinery. 1 Introduction Automatic time-complexity analysis is useful to the programmer for algorithmic considerations but has a special role in the development of efficient parallel programs [9, 6, 7, 12...