/Discuss this assignment. /Solutions are available.

1. Solve some recurrences

Give asymptotic (big-Theta) solutions to each of the following recurrences. You should assume in each case that for small n, T(n), if not otherwise specified, is some positive constant. Justify your answer in each case.

1. T(n) = 2T(n/2) + Theta(1).
2. T(n) = 2T(n/2) + Theta(log n).
3. T(n) = 2T(n/2) + Theta(n).

4. T(n) = 2T(n/2) + Theta(n²).

5. T(n) = 2T(n/2) + Theta(2ⁿ).

6. T(n) = 2T(n-1) + Theta(1).

7. T(n) = T(n-1) + Theta(n^1/2).

8. T(n) = T(n-1)², T(0) = 2.

Hint added after homework was distributed: The "standard" version of the Master Theorem that was shown in class and in SolvingRecurrences is required for some of these problems; the other version in LevitinBook is not strong enough. Here is another explanation of the "standard" Master Theorem.

2. Iron Prof

After experimenting with both paper and on-line course evaluation forms, a certain well-known university decides to replace both with televised head-to-head competition. Instructors at this university will now be judged by an Iron Prof competition narrated by William Shatner and judged by a panel of bored algorithms students. The initial plan is to have each new instructor do an impromptu lecture on a surprise topic in competition with each instructor previously hired by the university; this requires Theta(m) lectures if there are m previous hires.

1. Assume that the university starts with no instructors and hires n instructors, requiring the (m+1)-th instructor to do Theta(m) competitive lectures as described above. In big-Theta terms, how many lectures must the algorithms students sit through to judge the Iron Prof competition?

2. The algorithms students propose a new arrangement for the competition in which all professors are judged simultaneously in Theta(n^c) parallel lectures, for a constant c > 0 to be determined later. These lectures eliminate half of the professors; the surviving n/2 professors then go on to a new round of Theta((n/2)^c) lectures which eliminates half of the survivors, and so on recursively until only one winner is left. How large can c be for this procedure to require no more lectures (in asymptotic terms) than the original procedure?

3. Suppose that the second procedure above is put in place with c = 1, i.e. with Theta(n) lectures in the elimination phase. Now the algorithms students propose a competition in which the population of n professors is split into two groups of size n/2 each, a separate recursive competition is held within each group, and then Theta(n^k) lectures are held to choose the overall winner from the winners of the two groups. If the size n/2 competitions have the same recursive structure as the overall competition, how large can k be for this procedure to require no more lectures (in asymptotic terms) than the second procedure with c = 1?

In each case, justify your answer by writing and solving a recurrence for the total number of lectures.