The height of an AVL tree with 19 nodes must be 5. ( We assume that the height of a single node is 1).
Both AVL trees and red-black trees need at most O(1) rotations per insertion.
Consider the B+ trees of order MMM. There exists a constant c>0c > 0c>0 such that no matter how large MMM is, the running time of FINDKEY cannot be less than clog2nc\log_2 nclog2n where nnn is the number of the keys stored in the tree.
The longest simple path from a node xxx in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node xxx to a descendant leaf.
A binomial queue with 31 keys may consists of 6 binomial trees.
Backtracking always performs strictly better than bruteforce.
Consdier the activity selection (interval scheduling) problem. In class, we have proved that an optimal solution can be obtained by selecting the activities in increasing order of thier finishing time. We can also obtain an optimal solution by selecting the activities in decreasing order of their start time.
Consider the recurrence T(n)=aT(n/b)+ndT(n) = aT(n/b) + n^dT(n)=aT(n/b)+nd with T(1)=1T(1) = 1T(1)=1. If a<bda < b^da<bd, then T(n)T(n)T(n) is dominated (in asympototic sense) by the amount work at the root of the recursion tree. If a>bda > b^da>bd, then T(n)T(n)T(n) is dominated (in asympototic sense) by the total amount work at the leaves of the recursion tree.