1) Which of these statements is true of a binary search algorithm?

It cannot be performed in-place.

It will take a maximum of log(n) comparisons to find a value.

It will work on unsorted data.

It can be used to find values in a Linked List.

2) If you refactor an algorithm with time complexity of O(n) to be twice as fast, what would the new time complexity be?

O(log n)

O(1)

O(n^2)

O(n/2)

O(n)

 0 / \ 1 2 / \ \ 3 4 5 / / \ / \ 6 7 8 9 10

3) What order could a breadth-first traversal print the nodes in the tree above?

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

6, 3, 1, 7, 4, 8, 0, 2, 9, 5, 10

0, 2, 5, 10, 9, 1, 4, 8, 7, 3, 6

0, 1, 3, 6, 4, 7, 8, 2, 5, 9, 10

 0 / \ 1 2 / \ \ 3 4 5 / / \ / \ 6 7 8 9 10

4) What order would an in-order traversal print the nodes on this tree above?

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

0, 1, 3, 6, 4, 7, 8, 2, 5, 9, 10

0, 2, 5, 10, 9, 1, 4, 8, 7, 3, 6

6, 3, 1, 7, 4, 8, 0, 2, 9, 5, 10