2.3.1 Search and sort algorithms info

Question 1

how does a linear search work?

Answer 1

runs through each term in the array and compares it to the search item.
loops until the item is found or until the end of the list is reached.

Question 2

what is the time complexity of a linear search algorithm?

Answer 2

• worst case - item is not in list O(n)
• average case - O(n)
• best case - item is the first item in the list O(1)

Question 3

what is the space complexity of a linear search algorithm?

Answer 3

O(1)

Question 4

what does time complexity mean?

Answer 4

how well does the algorithm scale?
how does the number of steps grow as the input size (n) grows

Question 5

how does a binary search work?

Answer 5

the array is spit in half and the middle term is compared to the search item.
if the search item is less than the mid item, the right side of the array is discarded.
if the search item is greater than the mid term, the left side is discarded.
this is repeated until the item is found or there is only 1 item left.

Question 6

what is the condition for a binary search?

Answer 6

the array must be sorted

Question 7

what is the time complexity for a binary search algorithm?

Answer 7

• worst case - the item is not in the array O(logn)
• average case - O(logn)
• best case - item is at the midpoint O(1)

Question 8

what is the space complexity of a binary search algorithm?

Answer 8

O(1)

Question 9

how does a bubble sort work?

Answer 9

the first two terms are compared in size. if the second term is less than the first term, they are swapped.
this is done until the end of the array is reached.
this is one parse.
there are multiple parses to sort the array and a final parse to check if the array is sorted.

Question 10

what is the time complexity of a bubble sort algorithm?

Answer 10

• worst case - if the array is in reverse order O(n²)
• average case - O(n²)
• best case - the array is already sorted O(1)

Question 11

what is the space complexity of a bubble sort algorithm?

Answer 11

O(1)

Question 12

how does an insertion sort work?

Answer 12

the second term is compared to the one to the left of it. if it is less, the item on the left is shifted towards the right. this is continued until the item is inserted into the correct position

Question 13

what is the time complexity of an insertion sort algorithm?

Answer 13

worst case -

Question 14

what is the space complexity of an insertion sort algorithm?

Answer 14

O(1)

Question 15

how does a merge sort algorithm work?

Answer 15

• the array is split into two left and right sublists
• a merge sort is performed on the left and right sublists
• the sublists are split in half until they are one item
• the items are then merged together into sublists that are sorted
• this is repeated until the list is sorted

Question 16

what is the time complexity of a merge sort algorithm?

Answer 16

O(nlogn)

Question 17

what is the space complexity of a merge sort algorithm?

Answer 17

O(n)

Question 18

why is the space complexity of a merge sort algorithm what it is?

Answer 18

the space complexity = O(n)
this is because the set of variables will be created n times each time the merge sort is recursively called

Question 19

how does a quick sort algorithm work?

Answer 19

• choose an index to be the pivot
• put the items in the array that are less than the pivot on the left
• put the items in the array that are greater than the pivot on the right
• perform quick sorts on the left and right sublists
• repeat until all items have been a pivot

Question 20

what is the time complexity of a quick sort algorithm?

Answer 20

worst case - the items after the pivot are all less than or all greater than the pivot O(n²)
average case - O(nlogn)
best case - O(nlogn)

Question 21

what is the space complexity of a quick sort algorithm?

Answer 21

O(logn)