Advanced Data Structures and Algorithm Analysis Assessment 1(October 2013)

Part A
Answer in brief
1)Show that f(n) = (n +1)³ is O(n³).
2)Write the algorithm for Insertion sort and derive the time complexity for worst case.

Part B
Answer in detail.

1)

For the Above BST list out Inorder,Preorder and postorder traversal.
give pseudo code for performing Insertion and deletion in BST
2)List out the various asymptotic notations used to represent the complexity of an algorithm.State the signeficance of every notation.Compare and contrast the same.