Cruz, Donna, Midday On-Air Personality has reference to this Academic Journal, PHwiki organized this Journal Chapter 11 Limitations of Algorithm Power Copyright © 2007 Pearson Addison-Wesley. All rights reserved. Lower Bounds Lower bound: an estimate on a minimum amount of work needed to solve a given problem Examples: number of comparisons needed to find the largest element in a set of n numbers number of comparisons needed to sort an array of size n number of comparisons necessary as long as searching in a sorted array number of multiplications needed to multiply two n-by-n matrices Lower Bounds (cont.) Lower bound can be an exact count an efficiency class () Tight lower bound: there exists an algorithm with the same efficiency as the lower bound Problem Lower bound Tightness sorting (comparison-based) (nlog n) yes searching in a sorted array (log n) yes element uniqueness (nlog n) yes n-digit integer multiplication (n) unknown multiplication of n-by-n matrices (n2) unknown

This Particular University is Related to this Particular Journal

Methods as long as Establishing Lower Bounds trivial lower bounds in as long as mation-theoretic arguments (decision trees) adversary arguments problem reduction Trivial Lower Bounds Trivial lower bounds: based on counting the number of items that must be processed in input in addition to generated as output Examples finding max element – n steps or n/2 comparisons polynomial evaluation sorting element uniqueness Hamiltonian circuit existence Conclusions may in addition to may not be useful be careful in deciding how many elements must be processed Decision Trees Decision tree  a convenient model of algorithms involving comparisons in which: internal nodes represent comparisons leaves represent outcomes (or input cases) Decision tree as long as 3-element insertion sort