Big O - Array Sorting Algorithms Flashcards
What is the best time complexity of quicksort?
O(n log(n)) - bad
What is quicksort?
A divide and conquer algorithm where it divides the array into two smaller sub arrays. An index in each array is chosen as pivot, and the pivot compares itself to all the other entries so all smaller values are before it and all larger values are behind it. Recursively goes through each sub array (the one before and the one after the pivot position) and repeats.
What is the average time complexity of quicksort?
O(n log(n)) - bad
What is the worst time complexity of quicksort?
O(n^2) - terrible
What is the worst space complexity of quicksort?
O(log(n)) - good
What is merge sort?
A comparison based divide and conquer algorithm, where the list is divided into sublists of one element, then compared with an adjacent list to merge the two lists until it is sorted. A new array needs to be allocated to store the sorted list.
What is the best time complexity of merge sort?
O(n log(n)) - bad
What is the average time complexity of merge sort?
O(n log(n)) - bad
What is the worst time complexity of merge sort?
O(n log(n)) - bad
What is the worst space complexity of merge sort?
O(n) - okay
What is timsort?
An adaptive sorting algorithm designer by Tim Peters, where it identifies the longest “run” (sorted subarray) and chooses either insertion or merge sort.
What is the best time complexity of timsort?
O(n) - great!
What is the average time complexity of timsort?
O(n log(n)) - bad
What is the worst time complexity of timsort?
O(n log(n)) - bad
What is the worst space complexity of timsort?
O(n) - okay
What is heapsort?
The High-Level Idea
Heapsort is similar to selection sort—we’re repeatedly choosing the largest item and moving it to the end of our array. The main difference is that instead of scanning through the entire array to find the largest item, we convert the array into a max heap ↴ to speed things up.
Strengths
Fast. Heap sort runs in O(nlg(n))O(n\lg(n))O(nlg(n)) time, which scales well as nnn grows. Unlike quicksort, there’s no worst-case O(n2)O(n^2)O(n2) complexity.
Space efficient. Heap sort takes O(1)O(1)O(1) space. That’s way better than merge sort’s O(n)O(n)O(n) overhead.
Weaknesses
Slow in practice. While the asymptotic complexity of heap sort makes it look faster than quicksort, in real systems heap sort is often slower. (Remember, nnn and 2n2n2n are both O(n)O(n)O(n), even though the first is twice as fast as the second. Heap sort’s O(nlg(n))O(n\lg(n))O(nlg(n)) hides constant factors, but they still impact overall performance.)
Source: https://www.interviewcake.com/concept/java/heapsort
What is the best time complexity of heapsort?
O(n log(n)) - bad
What is the average time complexity of heapsort?
O(n log(n)) - bad
What is the worst time complexity of heapsort?
O(n log(n)) - bad
What is the worst space complexity of heapsort?
O(1) - great since it is done in place
What is bubble sort?
A simple algorithm that begins from the beginning of the list and compares adjacent pairs and swaps their position if not sorted. It repeatedly goes through the list, which grows shorter each time as the larger values get sorted to the end.
What is the best time complexity of bubble sort?
O(n) - good, only needs to go through once
What is the worst space complexity of bubble sort?
O(1) - great, done in place
What is the average time complexity of bubble sort?
O(n^2) - horrible
