For each of the following functions, indicate the class (g(n)) the functionbelongs to. (Use the simplest g(n) possible in your answers.) Prove yourassertions.a. (n3 + 1)6 b. √10n4 + 7n2 + 3nc. 2n lg(2n + 2)3 + (n2 + 2)2 lg n
Question
For each of the following functions, indicate the class (g(n)) the functionbelongs to. (Use the simplest g(n) possible in your answers.) Prove yourassertions.a. (n3 + 1)6 b. √10n4 + 7n2 + 3nc. 2n lg(2n + 2)3 + (n2 + 2)2 lg n
Solution
a. The function (n^3 + 1)^6 belongs to the class Θ(n^18). This is because when you raise n^3 to the power of 6, you multiply the exponents, resulting in n^18. The "+1" inside the parentheses and the constant 6 do not affect the order of growth, so we ignore them.
b. The function √(10n^4 + 7n^2 + 3n) belongs to the class Θ(n^2). This is because the highest power inside the square root is 4, and when you take the square root of n^4, you get n^2. The other terms inside the square root (7n^2 and 3n) are of lower order and do not affect the order of growth, so we ignore them.
c. The function 2n lg(2n + 2)^3 + (n^2 + 2)^2 lg n belongs to the class Θ(n^2 log n). This is because the highest order terms are n^2 and log n, and when you multiply them together, you get n^2 log n. The other terms (2n, lg(2n + 2)^3, and (n^2 + 2)^2) are of lower order and do not affect the order of growth, so we ignore them.
Similar Questions
List the following functions according to their order of growth from the lowestto the highest:(n2 + 3)!, 2 lg(n + 50)5, 33n , 0.05n10 + 3n3 + 1, ln 3 n, √n, 32n
For each of the following pairs of functions, indicate whether the first functionof each of the following pairs has a lower, same, or higher order of growth (towithin a constant multiple) than the second function.a. n(n + 1) and 2000n2 b. 100n2 and 0.01n3c. log 2 n and ln n d. log 22 n and log 2 n2e. 2n−1 and 2n f. (n − 1)! and n!
Let and .Find and simplify the functions and .a.)b.)c.)d.)
1. Why is f not a function from R to R ifa) f (x) = 1/x? b) f (x) =x ? c) f (x) =2 1x ?2. Determine whether f is a function from Z to R ifa) f (n) = ±n b) 2 1f n n c) 214f n n 3. Find these valuesa)1.1 b)0.1 c)4 d)3.2 e)5.2 e)2 e)1 22 3 4. Determine whether each of these functions from {a, b, c, d} to itself is one-to-one (onto)a) f (a) = b, f (b) = a, f (c) = c, f (d) = db) f (a) = b, f (b) = b, f (c) = d, f (d) = cc) f (a) = d, f (b) = b, f (c) = c, f (d) = d5. Determine whether each of these functions from Z to Z is one-to-one (onto)a) f (n) = n − 1 b) f (n) = n2 + 1 c) f (n) = n3 d) 2nf n 6. Determine whether f : Z × Z → Z is onto ifa) f (m, n) = 2m − n b) f (m, n) = m2 − n2 c) f (m, n) = m + n + 1d) f (m, n) = |m| − |n| e) f (m, n) = m2 − 4 f) f (m, n) = m + n7. Determine whether each of these functions is a bijection from R to R.a) f (x) = −3x + 4 b) f (x) = −3x2 + 7 c) f (x) = (x + 1)/(x + 2) d) f (x) = x5 + 18. Let S = {−1, 0, 2, 4, 7}. Find f (S) ifa) f (x) = 1 b) f (x) = 2x + 1 c) 5xf x
Given the functions f, of, x, equals, 5, x, cubedf(x)=5x 3 and g, of, x, equals, 12, dot, 3, to the power xg(x)=12⋅3 x , which of the following statements is true?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.