 3.2.1E: Determine whether each of these functions is O(x).a) f(x) = 10_____...
 3.2.2E: Determine whether each of these functions is O(x2).a) f(x)=17x +11_...
 3.2.3E: Use the definition of "f(x) is O(g(x))" to show that x4 + 9x3 + 4x ...
 3.2.4E: Use the definition of "f(x) is O(g(x))" to show that 2x + 17 is O(3x).
 3.2.5E: Show that (x2 + l)/(x + 1) is O(x).
 3.2.6E: Show that (x3 + 2x)/(2x + 1) is O(x2).
 3.2.7E: Find the least integer n such that f(x) is O(xn) for each of these ...
 3.2.9E: Show that x2 + 4x + 17 is O(x3) but that x3 is not O(x2 + 4x + 17).
 3.2.10E: Show that x3 is O(x4) but that x4 is not O(x3).
 3.2.11E: Show that 3x4 + 1 is O(x4/2) and x4/2 is O(3x4 + 1).
 3.2.12E: Show that x log x is O(x2) but that x2 is not O(x log x).
 3.2.13E: Show that 2n is O(3n) but that 3n is not O(2n). (Note that this is ...
 3.2.14E: Determine whether x3 is O(g(x)) for each of these functions g(x).a)...
 3.2.15E: Explain what it means for a function to be O(1).
 3.2.16E: Show that if f(x) is O(x). then f(x) is O(x2).
 3.2.17E: Suppose that f(x), g(x). and h(x) are functions such that f(x) is O...
 3.2.18E: Let k be a positive integer. Show that 1k + 2k + … + nk is O(nk+1).
 3.2.19E: Determine whether each of the functions 2n+l and 22n is O(2n).
 3.2.20E: Determine whether each of the functions log(n + 1) and log(n2 + 1) ...
 3.2.21E: Arrange the functions , 1000 log n, n log n, 2n!, 2n, 3n, and n2/1....
 3.2.22E: Arrange the function (1.5)n, n100, (log n)3, log n, 10n, (n!)2, and...
 3.2.23E: Suppose that you have two different algorithms for solving a proble...
 3.2.24E: Suppose that you have two different algorithms for solving a proble...
 3.2.25E: Give as good a bigO estimate as possible for each of these functio...
 3.2.26E: Give a bigO estimate for each of these functions. For the function...
 3.2.27E: Give a bigO estimate for each of these functions. For the function...
 3.2.28E: For each function in Exercise 1, determine whether that function is...
 3.2.29E: For each function in Exercise 2, determine whether that function is...
 3.2.30E: Show that each of these pairs of functions are of the same order.a)...
 3.2.31E: Show that f(x) is ? (g(x)) if and only if f(x) is O(g(x)) and g(x) ...
 3.2.32E: Show that if f(x) and g(x) are functions from the set of real numbe...
 3.2.33E: Show that if f(x) and g(x) are functions from the set of real numbe...
 3.2.34E: a) Show that 3x2 + x + 1 is ? (3x2) by directly finding the constan...
 3.2.35E: Express the relationship f(x) is ?(g(x)) using a picture. Show the ...
 3.2.36E: Explain what it means for a function to be ?(1).
 3.2.37E: Explain what it means for a function to be ? (1).
 3.2.38E: Give a bigO estimate of the product of the first n odd positive in...
 3.2.39E: Show that if f and g are realvalued functions such that f(x) is O(...
 3.2.40E: Show that for all real numbers a and b with a > 1 and b> 1, if f(x)...
 3.2.41E: Suppose that f(x) is O(g(x)) where f and g are increasing and unbou...
 3.2.42E: Suppose that f (x) is O (g (x) ). Does it follow that is 2f (x) is ...
 3.2.43E: Let f1(x) and f2(x) be functions from the set of real numbers to th...
 3.2.44E: Suppose that f(x), g(x), and h(x) are functions such that f(x) is? ...
 3.2.45E: If f1(x) and f2(x) are functions from the set of positive integers ...
 3.2.46E: Show that if f1(x) and f2(x) are functions from the set of positive...
 3.2.47E: Find functions f and g from the set of positive integers to the set...
 3.2.48E: Express the relationship f(x) is ?(g(x)) using a picture. Show the ...
 3.2.49E: Show that if f(x) is ?((g1(x)), f2(x)) is ? (g2(x)), and f2(x) ? 0 ...
 3.2.50E: Show that if f(x) = anxn + an1xn1 + a1x + a0, where a0, a1, … an...
 3.2.51E: Define the statement f(x, y) is ? (g(x, y)).
 3.2.52E: Define the statement f(x, y) is ? (g(x, y)).
 3.2.53E: Show that (x2 + xy + x log y)3 is O(x6y3).
 3.2.54E: Show that x5y3 + x4y4 + x3y5 is ? (x3y3).
 3.2.55E: BigO, bigTheta, And bigOmega notation can be extended to functio...
 3.2.56E: BigO, bigTheta, And bigOmega notation can be extended to functio...
 3.2.57E: BigO, BigTheta and BigOmega notation can be extended to function...
 3.2.58E: BigO, BigTheta and bigOmega notation can be extended to function...
 3.2.59E: (Requires calculus) Show that if d is positive and b > I, then nd i...
 3.2.60E: (Requires calculus) Show that if c > b > 1. then bn is O(cn) but cn...
 3.2.61E: (Requires calculus) Show thata) x2 is O(x3))________________b) x lo...
 3.2.62E: (Requires calculus)a) Show that if f(x) and g(x) are functions such...
 3.2.63E: (Requires calculus) Represent pictorially thatx logx is o(x2) by gr...
 3.2.64E: (Requires calculus) Express the relationship f(x) is o(g(x)) using ...
 3.2.65E: (Requires calculus) Suppose that f(x) is o(g(x)). DOes it follow th...
 3.2.66E: (Requires calculus) Suppose that f(x) is o(g(x)). Does it follow th...
 3.2.67E: (Requires calculus) The two parts of this exercise describe the rel...
 3.2.68E: (Requires calculus) Show that if f(x) is a polynomial of degree n a...
 3.2.69E: (Requires calculus) Show that if f1(x) is O(g(x)) and f2(x) is o(g(...
 3.2.70E: (Requires calculus) Let Hn be the nth harmonic number Show that Hn ...
 3.2.71E: Show that nlog n is ?(log n!).
 3.2.72E: Determine whether log n! is (n log n). Justify your answer.
 3.2.73E: Show that log n! is greater than (n log n)/4 for n > 4. [Hint: Begi...
 3.2.74E: (Requires calculus) For each of these pairs of functions, determine...
 3.2.75E: (Requires calculus) For each of these pairs of functions, determine...
Solutions for Chapter 3.2: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 3.2
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 3.2 includes 74 full stepbystep solutions. Since 74 problems in chapter 3.2 have been answered, more than 124789 students have viewed full stepbystep solutions from this chapter.

Column space C (A) =
space of all combinations of the columns of A.

Cross product u xv in R3:
Vector perpendicular to u and v, length Ilullllvlll sin el = area of parallelogram, u x v = "determinant" of [i j k; UI U2 U3; VI V2 V3].

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

Iterative method.
A sequence of steps intended to approach the desired solution.

Left inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

Length II x II.
Square root of x T x (Pythagoras in n dimensions).

Minimal polynomial of A.
The lowest degree polynomial with meA) = zero matrix. This is peA) = det(A  AI) if no eigenvalues are repeated; always meA) divides peA).

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

Orthogonal subspaces.
Every v in V is orthogonal to every w in W.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

Schwarz inequality
Iv·wl < IIvll IIwll.Then IvTAwl2 < (vT Av)(wT Aw) for pos def A.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Subspace S of V.
Any vector space inside V, including V and Z = {zero vector only}.

Toeplitz matrix.
Constant down each diagonal = timeinvariant (shiftinvariant) filter.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·