Automatic Complexity Analysis

    Research output: Chapter in Book/Report/Conference proceedingBook chapterResearch


    One way to analyse programs is to to derive expressions for their computational behaviour. A time bound function (or worst-case complexity) gives an upper bound for the computation time as a function of the size of input. We describe a system to derive such time bounds automatically using abstract interpretation. The semantics-based setting makes it possible to prove the correctness of the time bound function. The system can analyse programs in a first-order subset of Lisp and we show how the system also can be used to analyse programs in other languages.
    Original languageEnglish
    Title of host publicationFPCA '89 Conference on Functional Programming Languages and Computer Architecture.
    Number of pages13
    Place of PublicationLondon, England
    PublisherAssociation for Computing Machinery
    Publication date1989
    ISBN (Print)0-201-51389-7
    Publication statusPublished - 1989

    Cite this