536
Graphs and Trees
A decision tree argument can also be used to establish a lower bound on the
worst-case number of comparisons required to sort a list of n elements. As we did
for the search problem, let us see what we can say about a decision tree for sorting based on comparisons, regardless of the algorithm it represents. The leaves of
such a tree represent the final outcomes, that is, the various ordered arrangements
of the n items. There are n! such arrangements, so if p is the number of leaves in
the decision tree, then p ≥ n!. The worst case will equal the depth of the tree. But
it is also true that if the tree has depth d, then p ≤ 2
d
(Exercise 43 of Section 6.2).
Taking the base 2 logarithm of both sides of this inequality, we get log p ≤ d or,
because d is an integer, d =
tHeorem on The lower BounD For sorTinG
Any algorithm that sorts an n-element list by comparing pairs of items from the
list must do at least
proved that sorting n elements by comparing pairs of list items is bounded below
by Θ(n log n), whereas searching by comparing the target element to the list items
is bounded below by Θ(log n). As expected, it takes more work to sort than to
search.
S e c t i o n 6 . 3
review
tecHniQueS
• Draw decision trees for sequential search and binary search on n-element lists.
• Create a binary search tree.
main iDeaS
• Decision trees represent the sequences of possible
actions for certain algorithms.
• Analysis of a generic decision tree for algorithms
that solve a certain problem may lead to lower
bounds on the minimum amount of work needed to
solve the problem in the worst case.
• The task of searching an n-element list for a target
value x, if done by comparing x to elements in the
list, requires at least :log n; + 1 comparisons in the
worst case.
• The task of sorting an n-element list, if done by
comparing pairs of list elements, requires at least
:log n!; comparisons in the worst case.
W
W
exerciSeS 6.3
1. Draw the decision tree for sequential search on a list of three elements.
2. Draw the decision tree for sequential search on a list of six elements.
3. Draw the decision tree for binary search on a sorted list of seven elements. What is the depth of the tree?
4. Draw the decision tree for binary search on a sorted list of four elements. What is the depth of the tree?
Graphs and Trees
A decision tree argument can also be used to establish a lower bound on the
worst-case number of comparisons required to sort a list of n elements. As we did
for the search problem, let us see what we can say about a decision tree for sorting based on comparisons, regardless of the algorithm it represents. The leaves of
such a tree represent the final outcomes, that is, the various ordered arrangements
of the n items. There are n! such arrangements, so if p is the number of leaves in
the decision tree, then p ≥ n!. The worst case will equal the depth of the tree. But
it is also true that if the tree has depth d, then p ≤ 2
d
(Exercise 43 of Section 6.2).
Taking the base 2 logarithm of both sides of this inequality, we get log p ≤ d or,
because d is an integer, d =
tHeorem on The lower BounD For sorTinG
Any algorithm that sorts an n-element list by comparing pairs of items from the
list must do at least
proved that sorting n elements by comparing pairs of list items is bounded below
by Θ(n log n), whereas searching by comparing the target element to the list items
is bounded below by Θ(log n). As expected, it takes more work to sort than to
search.
S e c t i o n 6 . 3
review
tecHniQueS
• Draw decision trees for sequential search and binary search on n-element lists.
• Create a binary search tree.
main iDeaS
• Decision trees represent the sequences of possible
actions for certain algorithms.
• Analysis of a generic decision tree for algorithms
that solve a certain problem may lead to lower
bounds on the minimum amount of work needed to
solve the problem in the worst case.
• The task of searching an n-element list for a target
value x, if done by comparing x to elements in the
list, requires at least :log n; + 1 comparisons in the
worst case.
• The task of sorting an n-element list, if done by
comparing pairs of list elements, requires at least
:log n!; comparisons in the worst case.
W
W
exerciSeS 6.3
1. Draw the decision tree for sequential search on a list of three elements.
2. Draw the decision tree for sequential search on a list of six elements.
3. Draw the decision tree for binary search on a sorted list of seven elements. What is the depth of the tree?
4. Draw the decision tree for binary search on a sorted list of four elements. What is the depth of the tree?