What is the maximum/average number

of sequential searches needed?

The maximum number of sequential searches needed depends on your search.

There are different kinds of sequential searches:

1. Sequential or Linear Search

Max check + min checks = n

2

The formula to find out the maximum number would be

(n+1).

The formula to find out the average number would be

(n+1)/2.

Where n = the number of elements on the list

Number of Elements	Maximum Sequential	Avg Sequential
	n+1	(n+1)/2
10	11	5.5
15	16	8
20	21	10.5
50	51	25.5
100	101	50.5
150	151	75.5
1000	1001	500.5
1500	1501	750.5

Sequential Search of an unsorted array

There is not shorter way to sort an unsorted array because since the

element is in no specific place, the search has to go element by element.

2. Binary or Logarithmic Search

The formula to find out the maximum number would be

Log2n

The formula to find out the average number would be:

(Log2n)-1

Where n = the number of elements on the list)

3. Bubble Sort

Use this formula to find out the elements:

First-Last= n

UNTIL you have found the element you are looking.

This should only be when n>30.

Questions:

1. How many searches would be needed for 100?

a. 50.5

b. 101

c. 100

d. 89

2. How many searches are there?

a. 1

b. 2

c. 3

d. 4

3. What are the names of the searches?

a. bubble sort

b. sequential

c. binary

d. all of the above

4. Do all searches have the same amount of searches?

a. yes

b. no

c. maybe

d. Unsure

5. What is the formulas for the maximum number of searches for a sorted array?

6. What is the formula for the average number of searches?

Answers:

1. b 2. c. 3. d. 4. b. 5.(n+1) 6. (n+1)/2

Sources:

1. Searching and Sorting : http://copsewood.net/tic/dsalg4/sortsearch.html

2. Text Book: http://www.pkirs.utep.edu/cis3355/Textbook/textbook.htm

3. Advanced Placement Computer Science: http://www.thinkspot.net/materdei/apcompsci/SearchandSortAlgos/