Wk 2 Master Theorem, Merge Sort, Quick Sort Flashcards
What is the drag on merge sort?
It’s spatial complexity sucks because of many recursive calls and data kept on the stack.
What is the best we can do on comparison sort and why?
n lg n….(STBY)
What does the recurrence for insertion sort look like?
T(n) = T(n-1) + n //I think…
What are three parts of a recurrence that will determine the complexity of an algorithm?
Number of Subproblems
Size of Subproblems
Amount of work (work function at each level)
What is the characteristic function of a recursion? What is it telling me?
n^log.b(a).
It’s telling me how many subproblems I am split into at the very bottom of the tree. at the last level. The amount of work done there is the constant for each, so its the number of nodes which depends on the how many subproblems I was breaking along the way and how big those subproblems were.
What is the work function? What is it telling me?
it depends…. on f(n), but its the sum from i =0 to log.b(n-1) of a^i x f(n/b). basically, its the amount of work done in the tree. The amount of work done at each node of the level, the amount of nodes at that level, summed over all the levels.
Where can work from a recursion come from? How does this translate in the Master theorem? What are different cases of merge function vs. characteristic function?
Case 1 : All work happens at the bottom, with the smallest subproblems and thus the characteristic function drives.
f(n) q(n)
How is quicksort different from insertion sort?
Besides the complexity being n lg n vs. n^2. Quicksort also uses a partition and a recursive algorithm. In insertion sort, the first element may move around. For Q/S, once partition is made, that element does not move.
What is the general merge sort algorithm?
Partition the set.
Sort the left.
Sort the right.
When is Quicksort not efficient?
When we get a poor partition and we basically do not split the problem into a smaller subproblem.
What is the average case for quicksort? How does the running time of the average case compare to the worst case?
Average case, we’re thinking we’ll get a decent partition and it’s an n lg n algorithm. The worst case would be n^2, but since the avg case is a whole lot more likely than the worst case, its’ a good algorithm.
