Chapter 8: Q15E (page 567)
How many rounds are in the elimination tournament described in Exercise \(14\) when there are \(32\) teams?
Therefore, the number of rounds required is\(5\).
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Find\(f(n)\) when \(n = {2^k}\), where\(f\)satisfies the recurrence relation \(f(n) = 8f(n/2) + {n^2}\) with\(f(1) = 1\).
Give a big-O estimate for the number of comparisons used by the algorithm described in Exercise \(1{22}\).
50. It can be shown that \({C_B}\)the average number of comparisons made by the quick sort algorithm (described in preamble to Exercise 50 in Section 5.4), when sorting \(n\)elements in random order, satisfies the recurrence relation\({C_n} = n + 1 + \frac{2}{n}\sum\limits_{k = 0}^{n - 1} {{C_k}} \)
for \(n = 1,2, \ldots \), with initial condition \({C_0} = 0\)
a) Show that \(\left\{ {{C_n}} \right\}\)also satisfies the recurrence relation \(n{C_n} = (n + 1){C_{n - 1}} + 2n\)for \(n = 1,2, \ldots \)
b) Use Exercise 48 to solve the recurrence relation in part (a) to find an explicit formula for \({C_n}\)
(a) Set up a divide-and-conquer recurrence relation for the number of multiplications required to compute, where is a real number and is a positive integer, using the recursive algorithm from Exercise 26 in Section 5.4.
b) Use the recurrence relation you found in part (a) to construct a big- estimate for the number of multiplications used to compute using the recursive algorithm.
Find the solution to the recurrence relation,
\(f\left( n \right) = 3f\left( {\frac{n}{5}} \right) + 2{n^4}\),
When \(n\) is divisible by \(5\),
For \(n = {5^k}\)
Where \(k\) is a positive integer and
\(f\left( 1 \right) = 1\).
What do you think about this solution?
We value your feedback to improve our textbook solutions.
