Sorts + Searches + Big-O

Question 1

Big-O of Selection Sort (best case)

Answer 1

O(n^2)

Question 2

Big-O of Selection Sort (average case)

Answer 2

O(n^2)

Question 3

Big-O of Selection Sort (worst case)

Answer 3

O(n^2)

Question 4

Big-O of Insertion Sort (best case)

Answer 4

O(n)

Question 5

Big-O of Insertion Sort (average case)

Answer 5

O(n^2)

Question 6

Big-O of Insertion Sort (worst case)

Answer 6

O(n^2)

Question 7

Big-O of Merge Sort (best case)

Answer 7

O(nlogn)

Question 8

Big-O of Merge Sort (average case)

Answer 8

O(nlogn)

Question 9

Big-O of Merge Sort (worst case)

Answer 9

O(nlogn)

Question 10

Big-O of Quick Sort (best case)

Answer 10

O(nlogn)

Question 11

Big-O of Quick Sort (average case)

Answer 11

O(nlogn)

Question 12

Big-O of Quick Sort (worst case)

Answer 12

O(n^2)

Question 13

Big-O of Linear Search (best case)

Answer 13

O(1)

Question 14

Big-O of Linear Search (average case)

Answer 14

O(n)

Question 15

Big-O of Linear Search (worst case)

Answer 15

O(n)

Question 16

Big-O of Binary Search (best case)

Answer 16

O(1)

Question 17

Big-O of Binary Search (average case)

Answer 17

O(logn)

Question 18

Big-O of Binary Search (worst case)

Answer 18

O(logn)

Question 19

How does selection sort work?

Answer 19

Selection sort finds the largest item in the array, and swaps it to the end. The item that was previously at the end is now where the largest item used to be. Repeat with an array of length - 1.

Question 20

How does insertion sort work?

Answer 20

Insertion sort checks if the next item in the array is smaller than the item at the current index. If it is, it is moved to before the current index, and it checks again. IT DOES NOT SWAP!!

Question 21

How does merge sort work?

Answer 21

Merge sort splits the data in half until all that’s left are pairs. It then sorts the first two pairs, then combines them, then sorts them again. Then it moves on to the next two pairs and does the same thing. Then it combines both and sorts all 8 numbers, and so on.

Question 22

How does quick sort work?

Answer 22

Quick sort selects a pivot, which is the first item in the array. Then it moves from the left and from the right of the array until it finds two items that are bigger on the left and smaller on the right. It swaps them. Once the right pointer is less than the left pointer, the pivot and the item at the right pointer are swapped. The next pivot is chosen, and so on.

Question 23

How does linear search work?

Answer 23

Linear search uses one for loop to go through the entire array and check each item until it finds what it wants.

Question 24

How does binary search work?

Answer 24

Binary search compares the target to the middle item of the array. If it’s the same, it returns that location. If not, it either checks the top or bottom half of the array depending on how the target was in comparison to the middle, and recurs. It continues until the index finds the target or the first pointer is greater than the last.