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: Q32E (page 536)

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

Short Answer

Expert verified

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

Step by step solution

Define the Recursive formula

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

Prove the expression$f(n)$is$O\left( {{n^d}} \right)$

From exercise$31$, for $a \ne {b^d}$ and$n$is a power of$b$, then $f(n) = {C_1}{n^d} + {C_2}{n^{{{\log }_b}a}}$ for constants ${C_1}$and${C_2}$.

Now given$a < {b^d}$.

So,${\log _b}a < d$.

This gives$f(n) = {C_1}{n^d} + {C_2}{n^{{{\log }_b}a}} < \left( {{C_1} + {C_2}} \right){n^d} \in O\left( {{n^d}} \right)$.

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

Find$f(n)$ when $n = {2^k}$, where$f$satisfies the recurrence relation $f(n) = 8f(n/2) + {n^2}$ with$f(1) = 1$.

Use generating functions to solve the recurrence relation $a_{k} = 7 a_{k - 1}$ with the initial condition $a_{0} = 5$ .

Explain how generating functions can be used to find the number of ways in which postage of $r$ cents can be pasted on an envelope using 3-cent, 4-cent, and 20-cent stamps.

a) Assume that the order the stamps are pasted on does not matter.

b) Assume that the stamps are pasted in a row and the order in which they are pasted on matters.

c) Use your answer to part (a) to determine the number of ways 46 cents of postage can be pasted on an envelope using 3 -cent, 4-cent, and 20-cent stamps when the order the stamps are pasted on does not matter. (Use of a computer algebra program is advised.)

d) Use your answer to part (b) to determine the number of ways 46 cents of postage can be pasted in a row on an envelope using 3-cent, 4 -cent, and 20 -cent stamps when the order in which the stamps are pasted on matters.

To find number of edges and describe to make counting the edges easier.

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

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\(31\)to show that if\(a < {b^d}\), then\(f(n)\)is\(O\left( {{n^d}} \right)\).

Short Answer

Step by step solution

Define the Recursive formula

Prove the expression\(f(n)\)is\(O\left( {{n^d}} \right)\)

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Math Textbooks

Discrete Mathematics

Calculus

Pure Maths

Mechanics Maths

Applied Mathematics

Probability and Statistics

Study anywhere. Anytime. Across all devices.

Company

Product

Help