Chapter 8: Q11E (page 535)
Give a big- estimate for the function in Exercise 10 if is an increasing function.
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 a closed form for the generating function for each of these sequences. (For each sequence, use the most obvious choice of a sequence that follows the pattern of the initial terms listed.)
a) \(0,2,2,2,2,2,2,0,0,0,0,0, \ldots \)
b) \(0,0,0,1,1,1,1,1,1, \ldots \)
c) \(0,1,0,0,1,0,0,1,0,0,1, \ldots \)
d) \(2,4,8,16,32,64,128,256, \ldots \)
e) \(\left( {\begin{array}{*{20}{l}}7\\0\end{array}} \right),\left( {\begin{array}{*{20}{l}}7\\1\end{array}} \right),\left( {\begin{array}{*{20}{l}}7\\2\end{array}} \right), \ldots ,\left( {\begin{array}{*{20}{l}}7\\7\end{array}} \right),0,0,0,0,0, \ldots \)
f) \(2, - 2,2, - 2,2, - 2,2, - 2, \ldots \)
g) \(1,1,0,1,1,1,1,1,1,1, \ldots \)
h) \(0,0,0,1,2,3,4, \ldots \)
A sequence \({a_1},{a_2},.....,{a_n}\) is unimodal if and only if there is an index \(m,1 \le m \le n,\) such that \({a_i} < {a_i} + 1\) when \(1{1 < i < m}\) and \({a_i} > {a_{i + 1}}\) when \(m \le i < n\). That is, the terms of the sequence strictly increase until the \(m\)th term and they strictly decrease after it, which implies that \({a_m}\) is the largest term. In this exercise, \({a_m}\) will always denote the largest term of the unimodal sequence \({a_1},{a_2},.....,{a_n}\).
a) Show that \({a_m}\) is the unique term of the sequence that is greater than both the term immediately preceding it and the term immediately following it.
b) Show that if \({a_i} < {a_i} + 1\) where \(1 \le i < n\), then \(i + 1 \le m \le n\).
c) Show that if \({a_i} > {a_{i + 1}}\) where \(1 \le i < n\), then \(1 \le m \le i\).
d) Develop a divide-and-conquer algorithm for locating the index \(m\). (Hint: Suppose that \(i < m < j\). Use parts (a), (b), and (c) to determine whether \(((i + j)/2) + 1 \le m \le n,\) \(1 \le m \le ((i + j)/2) - 1,\) or \(m = ((i + j)/2)\)
Set up a divide-and-conquer recurrence relation for the number of modular multiplications required to compute \({a^n}\,\bmod \,\;m,\) where\(a,\;n\), and \(n\) are positive integers, using the recursive algorithms from Example 4 in Section 5.4.
b) Use the recurrence relation you found in part (a) to construct a big-\(O\)estimate for the number of modular multiplications used to compute\({a^n}\,\bmod \,\;m\)using the recursive algorithm.
Solve the recurrence relation if and . (See the hint for Exercise 9.)
Give a big- \(O\) estimate for the function\(f\)in Exercise\(36\)if\(f\)is an increasing function.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
