Answer to Question #45498 in Programming & Computer Science for Naf

Question

1. Explain briefly how to insert a given key in a binary search tree

2. Find following questions are True or False? If false write the correct answer:
a. The insertion operation in a binary search tree has a running time of O(1) in the worst case.
b. In a stack implemented using an array, the push operation is O(log n) in the worst case.
(Assume the array is not full)
c. n^2 logm + n^3 is O(n^3)
d. n^2 + n^3 = O(n^3)
e. If we sort n numbers using quicksort, then the worst case running time is O(n).
f. A (2,4) tree is also a binary search tree.
g. The height of a red black tree with n entries, is always less than the height of every binary
search tree on the same set of entries.
h. An undirected graph with n vertices has at least n edges.
i. An undirected graph with n vertices and n + 2 edges must always contain a cycle.
j. The worst case running time of sorting n elements using heapsort is O(n log n)