Open In App

Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Discrete Mathematics and its Applications

Kenneth H. Rosen

$Math Studyset Vaia Explanations$ Math

7th Edition · 808 pages

ISBN: 9780073383095

Chapter 8: Q30E (page 536)

Use Exercise 29 to show that if $a = {b^d}$, then $f(n)$ is $O\left( {{n^d}\log n} \right)$.

Short Answer

Expert verified

The expression$f(n) = O\left( {{n^d}\log n} \right)$is proved.

Step by step solution

Define Recursive formula

A recursive formula is a formula that defines any term of a sequence in terms of its preceding terms.

Solve by recursive procedure on $f(n)$

It is easy to see that since $f(n) = {n^d}f(1) + c{n^d}{\log _b}n$, by exercise$29$, we have $f(n) = O\left( {{n^d}\log n} \right)$.

This is because $f(1)$ and$c$are constants and ${n^d}\log n$ grows faster than${n^d}$.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example 5?

Give a combinatorial interpretation of the coefficient of $x^{4}$ in the expansion ${(1 + x + x^{2} + x^{3} + \dots)}^{3}$ . Use this interpretation to find this number.

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}$

Suppose that $c_{1}, c_{2}, \dots, c_{p}$ is a longest common subsequence of the sequences $a_{1}, a_{2}, \dots, a_{m}$ and $b_{1}, b_{2}, \dots, b_{n}$ .
a) Show that if $a_{m} = b_{n}$ , then $c_{p} = a_{m} = b_{n}$ and $c_{1}, c_{2}, \dots, c_{p - 1}$ is a longest common subsequence of $a_{1}, a_{2}, \dots, a_{m - 1}$ and $b_{1}, b_{2}, \dots, b_{n - 1}$ when $p > 1$ .
b) Suppose that $a_{m} \neq b_{n}$ . Show that if $c_{p} \neq a_{m}$ , then $c_{1}, c_{2}, \dots, c_{p}$ is a longest common subsequence of $a_{1}, a_{2}, \dots, a_{m - 1}$ and $b_{1}, b_{2}, \dots, b_{n}$ and also show that if $c_{p} \neq b_{n}$ , then $c_{1}, c_{2}, \dots, c_{p}$ is a longest common subsequence of $a_{1}, a_{2}, \dots, a_{m}$ and $b_{1}, b_{2}, \dots, b_{n - 1}$

Find a closed form for the generating function for each of these sequences. (Assume a general form for the terms of the sequence, using the most obvious choice of such a sequence.)

a) $ - 1, - 1, - 1, - 1, - 1, - 1, - 1,0,0,0,0,0,0, \ldots $

b) $1,3,9,27,81,243,729, \ldots $

c) $0,0,3, - 3,3, - 3,3, - 3, \ldots $

d) $1,2,1,1,1,1,1,1,1, \ldots $

e) $\left( {\begin{array}{*{20}{l}}7\\0\end{array}} \right),2\left( {\begin{array}{*{20}{l}}7\\1\end{array}} \right),{2^2}\left( {\begin{array}{*{20}{l}}7\\2\end{array}} \right), \ldots ,{2^7}\left( {\begin{array}{*{20}{l}}7\\7\end{array}} \right),0,0,0,0, \ldots $

f) $ - 3,3, - 3,3, - 3,3, \ldots $

g) $0,1, - 2,4, - 8,16, - 32,64, \ldots $

h) $1,0,1,0,1,0,1,0, \ldots $

See all solutions

Recommended explanations on Math Textbooks

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free

Use Exercise 29 to show that if \(a = {b^d}\), then \(f(n)\) is \(O\left( {{n^d}\log n} \right)\).

Short Answer

Step by step solution

Define Recursive formula

Solve by recursive procedure on \(f(n)\)

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Math Textbooks

Discrete Mathematics

Geometry

Statistics

Logic and Functions

Probability and Statistics

Applied Mathematics

Study anywhere. Anytime. Across all devices.

Company

Product

Help