Class Notes (834,986)
Canada (508,846)
York University (35,167)
ITEC 2620 (2)


5 Pages
Unlock Document

Information Technology
ITEC 2620
Stephen Chen

York University AP/ITEC 2620 3.0 INTRODUCTION TO DATA STRUCTURES Assignment Prof. S. Chen Surname: __________________ _________________ Given Names: ___________________________________ Student Number: ___________________________________ 1 Total 2 3 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 elements? Explain. 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
More Less

Related notes for ITEC 2620

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.