CSE 2050 Time Complexities Test with Correct Verified Answers| Latest 2024

CSE 2050 Time Complexities Test with Correct Verified Answers | Latest 2024 Start at the beginning, sort the first 2 items in the list. Then, going through the list, add each next item into the sorted list, where it is supposed to be - Insertion sort Quick sort best case - O(nlogn) Quick sort average case - O(nlogn) Quick sort worst case - O(n^2) Quick sort works best on - good pivots (close to median) Quick sort works worst on - bad pivots (close to edges) quick sort properties - dependent on pivots, recursive Pick a random ele ment as a pivot, move everything less than that element to it's left, and everything greater to it's right. Then, repeat this for the left and the right halves, picking a pivot and moving things around accordingly - quick sort Merge sort best case - O(nlo gn) Merge sort average case - O(nlogn) Merge sort worst case - O(nlogn) Merge sort works best when - already almost sorted list merge sort works worst on - reverse order list merge sort properties - recursive divide a list continuously into smaller s ublists, until you end with just one element in a list. merge sublists, sorting while you do, until you end up with just one sorted list - merge sort Cuts a SORTED list in half, checks the edge of each half to see if it matches the item searching for. The n cuts the half where the item we want would be, and continuous cutting in half until we find the item. - Binary search Binary search best case - O(1) Binary search average case - O(log n) Binary search worst case - O(log n) Loops through a list, once you find the element you are searching for you stop - linear search