Problem 1 Analysis of recurrence trees. Find the nice non-recursive function f (

Question

Problem 1

Analysis of recurrence trees. Find the nice non-recursive function f ( n ) such that T ( n ) =? ( f ( n )). Show your work: what is the number of levels, number of instances on each level, work of each instance and the total work on that level.

a) T ( n ) = 3 T ( n /2 ) + n 2 lg n

b) T ( n ) = 3 T ( n /2 ) + n lg n

c) T ( n ) = ? nT ( ? n ) + n

d) T ( n ) = ? nT ( ? n ) + 1

Problem 2

Use a program to simulate this process one million times for 100 candidates. Submit the program and the results.

a) How frequently we make 10 offers or more?

b) Suppose that we can afford to make at most 6 offers, so either we do not see 6 candidates that are better than all previous ones (i.e. 6 improvements of our selection), and thus we make the best possible selection, or we see the 6-th improvement and this is our final choice. What is the average number of better selections that the choice we have made?

Explanation / Answer

T(n) = 3T(n=2) + n

There are 3i nodes at depth i, each with value n=2i , so the level-by-level sum () is an

increasing geometric series:

T(n) =

XL

i=0

(3=2)in.

This geometric series is dominated by its final term (3=2)Ln. Each leaf contributes 1 to

this term; thus, the final term is equal to the number of leaves in the tree! The recursion

tree has L = log2 n levels, and therefore 3log2 n = nlog2 3 leaves, so T(n) = (nlog2 3).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.