A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms.
Lars ArgeMikael B. KnudsenKirsten LarsenPublished in: WADS (1993)
Keyphrases
- lower bound
- worst case
- computational complexity
- learning algorithm
- data structure
- computationally hard
- upper and lower bounds
- upper bound
- significant improvement
- computational cost
- benchmark datasets
- space complexity
- scheduling problem
- special case
- theoretical analysis
- orders of magnitude
- times faster
- branch and bound algorithm
- query processing
- high computational complexity
- previously studied
- lower complexity
- optimal solution