1. Write T or F for each of the following statements to indicate whether the statement is true or false, respectively, and briefly explain why. Your justification is worth more points. (2 points)

1. Suppose that every operation on a data structure runs in O(1) amortized time. Then the running time for performing a sequence of n operations on an initially empty data structure is O(n) in the worst case.

2. Index-Sort is always faster than insertion-sort. ( )

3. All the problems with optimal substructure can be solved by dynamic programming efficiently. ( )

4. Optimal BST is always a balanced binary-search tree. ( )