Deducing the asymptotic behavior of a function from its behavior on a subsequence
By: Daniel Davis and Hartmut Huber
Contributors: Huber, Hartmut; Naval Postgraduate School (U.S.)
Publisher: Naval Postgraduate School
Published: 1986
Place of publication: Monterey, California
Language: eng
Number of pages: 12
Subjects: Functions
Description: This paper investigates the relations between two complexity functions when they have the same order class on a subsequence.  Sufficient conditions are derived for concluding that two functions have the same order class if they are sufficiently related on a subsequence.  These theoretical results are used to prove order class properties of complexity functions arising from divide and conquer problems.  In addition, it is shown that between any two comparable non-constant order classes there are order classes that are incomparable.
Notes: Title from cover.

"Prepared for: Chief of Naval Research"--Cover.

"November 1986"--Cover.

"NPS52-86-024"--Cover.

Includes bibliographical references (p. 12)

"Approved for public release; distribution unlimited"--Cover.

Technical report; 1986.

kmc/kmc 11/4/09.

aq/aq cc:9116 02/27/98