ITEC 2620 Lecture Notes - Quicksort, Binary Search Algorithm, Linked List

• School: York University
• Department: Information Technology
• Course: ITEC 2620
• Professor: Stephen Chen

Document Summary

Question 1 (15 marks) short answer (maximum 20 words): 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. Give an example for algorithm a and algorithm b. Part e (3 marks): an implementation of quicksort has its worst case of o(n2) for an array in sorted order. Explain how this is possible/how this version of quicksort was implemented. Assume that an array has n random values. What is the time complexity of the following method that makes every element in the array equal to the largest element in the original array. Write a recursive function that will calculate the height of a binary tree. Note: root1 and root2 are instances of the class binnode: root2.