Question

1) (10 pts) What are the worst case run times of each of the following operations? Make sure to list your answer in terms of the appropriate variables in the prompt. Note that on occasion, some of the run times won't be dependent on some of the variables listed in the prompt. (a) Inserting an item to the front of a linked list of n elements. (b) Sorting n integers using Quick Sort. (c) Merging a sorted list of a elements with a sorted list of b elements. (d) Inserting an item into a binary heap of n elements. (e) Deleting an item from a binary search tree of n elements. (1) Deleting an item from an AVL tree of n elements. (g) Printing out each permutation of n elements, where printing one value takes O(1) time. (h) Calculating a mod e where individual multiplications and mods take O(1) time, using fast modular exponentiation. (1) A floodfill on a grid with r rows and c columns. (1) Dequeuing an item from a queue of n elements.

Answer 1

a) O(1)

b) O(n^2)

c) O(n)

d) O(log(n))

e) O(n)