AP/ITEC 2620 3.0
INTRODUCTION TO DATA STRUCTURES
Prof. S. Chen
Surname: __________________ _________________
Given Names: ___________________________________
Student Number: ___________________________________
Page 1 of 5 Question 1 (15 marks) Short Answer (maximum 20 words):
Answer all five parts below.
Part A (3 marks): What is the worst case time complexity for binary search on a BST with n
Part B (3 marks): The first time you run algorithm A on a dataset of n elements; it is faster than
algorithm B. The second time you run algorithm A on a dataset of n elements; it is slower than
algorithm B. Explain how this is possible. Give an example for algorithm A and algorithm B.
Part C (3 marks): If both have n nodes and are sorted smallest to largest, will it be faster to find
the largest value in a sorted linked list or a minimum-level BST? Explain.
Part D (3 marks): What is the time complexity to dele te the root of a minimum-level BST with
n nodes? Explain.
Part E (3 marks): An implementation of quicksort has its worst case of O(n 2) for an array in
sorted order. Explain how this is possible/how this version of quicksort was implemented.
Page 2 of 5 Question 2 (10 marks) Complexity Analysis/Estimation:
Assume that an a