Big THETA of sorts
Insertion,selection,Bubble (n^2)
Heap, merge, quick
Method you call after deleting the root node
Heapify
Is merge sort stable T/F
Position of pivot according to sudo code given in slides
Last element
If c < log_b a then what case are we in
Case 1
Big theta of merge sort in the worse case
n log n
(Same answer for all cases)
What are the requirements for a complete binary tree
Every level except the last one is completely filled and the last level is filled from left to right
Does merge sort use an auxiliary array T/F
True
What will the value of t be after a partition
The location of the pivot would be swapped with or the first number that is strictly greater than the pivot (you swap if the pivot is equal to the number)
T(n) = 16T (n/4) + n
Case 1
BigTheta(n^2)
Best bigTheta we can get for comparison based sorting algorithim in the worst case
n log n
Merge Sort or Heap sort
Difference between max heap and min heap
For max heap the nodes value is greater than its 2 child while for min heap the nodes value is less than its 2 children
T(n) = 2T (n/2) + n log n
Case 2
BigTheta (n (log n)^2)
Name the two sorts that have the same big Theta for all cases. Then which is faster
Selection and Merge sort
Selection BigTheta(n^2)
Merge BigTheta(n log n)
what is the height of a binary tree when you know the number of nodes
log(n+1) - 1
T(n) = 64T(n/4) + nn1/2 log n
Case 2 Fancy
Big Theta( n3/2(log n)^2 )
Name the 3 sorts that have best case of Big theta (n)
Bubble, Selection, Insertion, Heap, Merge, Quick
Heap, Bubble, Insertion
What is the answer
T(n) = 6T (n/3) + n^2 log n
Case 3
Big Theta (n^2 log n)