Skip to main content
Engineering LibreTexts

21.5: Glossary

  • Page ID
  • analysis of algorithms:
    A way to compare algorithms in terms of their run time and/or space requirements.
    machine model:
    A simplified representation of a computer used to describe algorithms.
    worst case:
    The input that makes a given algorithm run slowest (or require the most space).
    leading term:
    In a polynomial, the term with the highest exponent.
    crossover point:
    The problem size where two algorithms require the same run time or space.
    order of growth:
    A set of functions that all grow in a way considered equivalent for purposes of analysis of algorithms. For example, all functions that grow linearly belong to the same order of growth.
    Big-Oh notation:
    Notation for representing an order of growth; for example, \( O(n) \) represents the set of functions that grow linearly.
    An algorithm whose run time is proportional to problem size, at least for large problem sizes.
    An algorithm whose run time is proportional to \( n^2 \), where \( n \) is a measure of problem size.
    The problem of locating an element of a collection (like a list or dictionary) or determining that it is not present.
    A data structure that represents a collection of key-value pairs and performs search in constant time.