CSCI 132 Data Structures

Name:

Laboratory 8 Answer Sheet for part 2.

2. Comparing Search functions

a. What is the average number of comparisons made for each algorithm for the following values of n: 5, 10, 20, 100, 1000 ? Put your answers in table form as follows:

List Length	n = 5	n = 10	n = 20	n = 100	n = 1000
Successful:
Sequential
Binary 1
Binary 2
Unsuccessful:
Sequential
Binary 1
Binary 2

b. Explain your results for part a for a list length of 100 based on the formulas for the running time of each of the search algorithms given in the text. Do your results match what you would predict from these formulas?

Sequential search (successful): (1/2)(n + 1)

Sequential search (unsuccessful): n

binary_search_1 (successful and unsuccessful): lg(n) + 1

binary_search_2 successful: (2(n+1)/n) lg(n+1) -3 =~ 2lg(n) -3

binary_search_2 unsuccessful: 2lg(n)

Note: log₁₀(n) == log₁₀(2)*log₂(n),
so log₂(n) == (log₁₀(n))/log₁₀(2) = 3.32*log₁₀(n)
Use the notation that lg(n) is log₂(n).

Results and expected values for n = 100:

	Computed	Expected	Formula
Successful:
Sequential
Binary 1
Binary 2
	Computed	Expected	Formula
Unsuccessful:
Sequential
Binary 1
Binary 2

Parts c - e: Run the search_compare program to answer questions in parts c - e. You will need to test multiple values of n to answer the questions.

c. For what values of n does sequential search do fewer average comparisons than binary_search_1 for successful searches? For unsuccessful searches? (Consider all possible values of n > 0 in your answer, not simply the values given in part a)

Successful searches:

Unsuccessful searches:

d. For what values of n does sequential search do fewer average comparisons than binary_search_2 for successful searches? For unsuccessful searches? (Consider all possible values of n > 0 in your answer).

Successful searches:

Unsuccessful searches:

e. For what values of n does binary_search_2 do fewer average comparisons than binary_search_1 for successful searches? For unsuccessful searches? (Consider all possible values of n > 0 in your answer).

Successful searches:

Unsuccessful searches:

f. Draw the comparison trees for binary_search_1 and binary_search_2 for n = 7. (Use a separate sheet if necessary)