CSE 241: More Decision Tree Lower Bound Practice Problems
-
Prove the best lower bound you can (using the decision tree technique)
on the time complexity of the problem of finding the minimum
value and the maximum value in an array A with n
distinct elements under the model of computation in which you can only
access elements from array A by asking if A[i] < A[j] for i and
j integers from 0 to n-1.
solution
- Prove the best lower bound you can (using the decision tree
technique) for the number of
comparisons required by a comparison based algorithm to merge
a sorted list of n items with a sorted list of 2 items.
solution