Invitation: Chapter 3

Question 1

When doing a sequential search, what are the best, worst, and average cases?

Answer 1

Best=1
Worst=n
Average=n/2

Question 2

How does binary search work?

Answer 2

We look in the middle, decide which way to go, look in the middle of that part, decide which way to go within the part, and keep repeating this pattern until we have found what we are looking for

Question 3

What is the worst case in a binary search? What is the average case?

Answer 3

worst case=lg n

average case=(also) lg n(although exact value is smaller than in the worst case)

Question 4

Pattern Matching: what is the best case?

2 cases

Answer 4

1: what we are looking for is the first pattern on the list.
2: the first pattern of what we are looking for appears nowhere on the list

Question 5

Pattern Matching: what is the worst case?

2 cases

Answer 5

1: the pattern we are looking for appears continuously throughout the whole list, but never completely
2: the pattern appears absolutely everywhere on the list

Question 6

explain selection sort algorithm

Answer 6

We have a list of numbers, and draw a vertical line at the far end of the list. The left side of this line represents the unsorted numbers. The right side represents the sorted numbers. Take the largest number on the unsorted side and switch it with the right-most number. Then move the vertical line one to the left. Repeat this process until there are no more numbers on the unsorted side.

Question 7

What are the best, worst, and average cases of the selection sort algorithm?

Answer 7

There are none, since there is only one result:

((1/2)n^2)-(1/2)n