My library button

No image available

Deducing the Asymptotic Behavior of a Function from Its Behavior on a Subsequence

by Daniel Lee Davis ยท 1986

ISBN:  Unavailable

Category: Unavailable

Page count: 12

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.