On the Complexity of Linear Search Tree Programs for Searching (Extended Abstract).

Abstract

A set of general tools are obtained for proving nontrivial lower bounds on the class of linear search trees. Among them is an n squared lower bound on the classic knapsack problem. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1975
Accession Number
ADA039585

Entities

People

  • David Dobkin
  • Richard J. Lipton

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Automata
  • Automata Theory
  • Computations
  • Computer Languages
  • Computer Programming
  • Computer Science
  • Computers
  • Formal Languages
  • Information Retrieval
  • Military Research
  • Numerical Analysis
  • Operations Research
  • Pattern Recognition
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Operations Research