Question

standardized test questions
you may use a graphing calculator to solve the following problems.

1. true or false a search of order ( n log_2 n ) is more efficient than a search of order ( n^{3/2} ). justify your answer.
2. true or false the function ( f(x) = 100x^2 + 50x + 1 ) grows faster than the function ( x^2 + 1 ) as ( x \to infty ). justify your answer.
3. multiple choice which of the following functions grows faster than ( x^5 + x^2 + 1 ) as ( x \to infty )?

(a) ( x^2 + 1 ) (b) ( x^3 + 2 ) (c) ( x^4 - x^2 ) (d) ( x^5 ) (e) ( x^6 + 1 )

1. multiple choice which of the following functions grows slower than ( log_{13} x ) as ( x \to infty )?

(a) ( e^{-x} ) (b) ( log_2 x ) (c) ( ln x ) (d) ( log x ) (e) ( x ln x )

Explanation:

Question 46

Step1: Recall Asymptotic Growth

To compare \( n\log_2 n \) and \( n^{3/2} \), analyze their growth rates. For large \( n \), compare the exponents (or use limits).

Step2: Analyze Growth Rates

The function \( n^{3/2} = n^{1.5} \), and \( n\log_2 n \) grows slower than \( n^{1.5} \) (since \( \log n \) grows much slower than \( n^{0.5} \) for large \( n \)). A search with lower order is more efficient. So \( n\log_2 n \) (order \( O(n\log n) \)) is more efficient than \( O(n^{3/2}) \).

Step1: Recall Polynomial Growth

For polynomials, the leading term (highest degree term) determines growth. Both \( f(x)=100x^2 + 50x + 1 \) and \( g(x)=x^2 + 1 \) are degree 2 polynomials.

Step2: Compare Leading Terms

The leading term of \( f(x) \) is \( 100x^2 \), and of \( g(x) \) is \( x^2 \). But for large \( x \), the ratio \( \frac{f(x)}{g(x)}=\frac{100x^2 + 50x + 1}{x^2 + 1}\to 100 \) (a constant), not infinity. So they grow at the same rate (as \( x\to\infty \)). Thus, \( f(x) \) does not grow faster than \( g(x) \).

Step1: Recall Polynomial Growth

A function \( f(x) \) grows faster than \( g(x) \) if \( \lim_{x\to\infty}\frac{f(x)}{g(x)}=\infty \). For polynomials, the higher degree function grows faster.

Step2: Analyze Each Option

• (A) \( x^2 + 1 \): Degree 2 < 5 (of \( x^5 + x^2 + 1 \)) → Slower.
• (B) \( x^3 + 2 \): Degree 3 < 5 → Slower.
• (C) \( x^4 - x^2 \): Degree 4 < 5 → Slower.
• (D) \( x^5 \): Degree 5 (same as leading term of \( x^5 + x^2 + 1 \)) → Grows at same rate.
• (E) \( x^6 + 1 \): Degree 6 > 5 → Grows faster.

Answer:

True

Question 47