Mathematics for Computer Science

Chapter 21 Recurrences890

constantn. State the value ofpyou get for each recurrence (which can be left in the
form of logs). Also, state the values of theai;bi;andhi.n/for each recurrence.

1.T.n/D3T.bn=3c/Cn.

2.T.n/D4T.bn=3c/Cn^2.

3.T.n/D3T.bn=4c/Cn.

4.T.n/DT.bn=4c/CT.bn=3c/Cn.

5.T.n/DT.dn=4e/CT.b3n=4c/Cn.

6.T.n/D2T.bn=4c/C

p

n.

7.T.n/D2T.bn=4cC1/C

p

n.

8.T.n/D2T.



n=4C

p

n

̆

/C 1.

9.T.n/D3T.

l

n1=3

m

/Clog 3 n. (For this problem,T.2/D 1 .)

10.T.n/D

p

eT.

j

n1=e

k

/Clnn.

Class Problems

Problem 21.3.
We have devised an error-tolerant version ofMergeSort. We call our exciting new
algorithmOverSort.
Here is how the new algorithm works. The input is a list ofndistinct numbers.
If the list contains a single number, then there is nothing to do. If the list contains
two numbers, then we sort them with a single comparison. If the list contains more
than two numbers, then we perform the following sequence of steps.

 We make a list containing the first^23 nnumbers and sort it recursively.

 We make a list containing the last^23 nnumbers and sort it recursively.

 We make a list containing the first^13 nnumbers and the last^13 nnumbers and

sort it recursively.

 We merge the first and second lists, throwing out duplicates.

 We merge this combined list with the third list, again throwing out duplicates.