Let A be an array representing a permutation of {1, . . . , n}. Consider the
Fantastic news! We've Found the answer you've been seeking!
Question:
Let A be an array representing a permutation of {1, . . . , n}. Consider the following recursive procedure for building a binary tree: Let j be the index of holding the minimum value in A, we put A[j] at the root of the tree, we set its left child to be the subtree recursively defined by A[0, . . . , j − 1] and its right child to be the subtree recursively defined by A[j + 1, . . . , n − 1]. Let H(n) be the expected height of a tree generated by a random permutation. Run experiments to make a conjecture about the asymptotic growth of H(n). Your task is to find a function f(n) and verify experimentally that limn→∞H(n)f(n)) is a constant. Write a short justification (must include a plot) of your conjecture.
Related Book For
Posted Date: