2.3.1 Algorithms

Question 1

What is the time complexity of a binary search?

Answer 1

O (log n)

Question 2

What is the time complexity of a linear search?

Answer 2

O (n)

Question 3

What are the steps for a binary search?

Answer 3

1. Start at the middle item in the list
2. If the middle item is the one to be found, the search is complete.
3. If the item to be found is lower than the middle item, discard all items to the right.
4. If the item to be found is higher than the middle item, discard all items to the left.
5. Repeat from step 2 until you have found the item or there are no more items in the list.
6. If the item has been found, output item data. If it has not, output “not found.”

Question 4

What are the steps for an insertion sort?

Answer 4

1. Start at the second item in the list.
2. Compare current item with the first item in the sorted list.
3. If the current item is greater than the item in the list, move to the next item in the sorted list.
4. Repeat from step 3 until the position of the current item is less than or equal to the item in the sorted list.
5. Move all the items in the list from the current position up one place to create a space for the current item.
6. Insert the current item.
7. Repeat from step 2 with the next item in the list until all the items have been inserted.

Question 5

What is the time complexity for the insertion sort?

Answer 5

O (n^2)

Question 6

What are the steps for a merge sort?

Answer 6

1. Repeatedly divide the list in half into two smaller lists until each item is in its own list.
2. Take two adjacent lists and start with the first item in each one.
3. Compare the two items.
4. Insert the lowest item into a new list. Move to the next item in the list it was taken from.
5. Repeat step 4 until all the items from one of the lists have been put into the new list.
6. Append all the items from the list still containing items to the new list.
7. Remove both old lists.
8. Repeat from step 2 until only one list remains

Question 7

What is the time complexity for a merge sort?

Answer 7

O (n logn)

Question 8

What are the steps in quicksort?

Answer 8

1. Set the pivot value as the first item in the list.
2. Set a pointer to the second and last items in the list.
3. While the second pointer is greater than or equal to the first pointer:
   a. Whilst the first pointer is less than or equal to the second pointer and the item at the first pointer is less than or equal to the pivot value, increase the first pointer by one.
   b. Whilst the second pointer is greater than or equal to the first pointer and the item at the second pointer is greater than or equal to the pivot, decrease the second pointer by one.
   c. If the second pointer is greater than the first pointer, swap the items.
4. Swap the pivot value with the item at the second pointer.
5. Repeat from step 1 on the list of items to the left of the second pointer

Question 9

What is the time complexity of quicksort?

Answer 9

O (n logn)