1. For each of the following functions, find a function g(n) such that f(n) (g(n
ID: 668995 • Letter: 1
Question
1. For each of the following functions, find a function g(n) such that f(n) (g(n)). You must use the simplest g(n) possible in your answers such as n, log(n), nlog(n), n^2, n^3, an, and product of them. Prove your assertion. (20pts) Hints: You can either use the definition of big- or use the limit.
a. (n^3 + 1)^2
b. sqrt(9n) + 9 log(n)
c. 2n * log(n^2) + (n +1)^2 * log(n)
d. 3^(n+2) + 4^(n2)
//************************************************************************************************
3. Find the order of growth of the following sums. You need to indicate the class (g(n)) the function belongs to. You must use the simplest g(n) possible in your answers. (20pts)
a. (i^2 + 1)^2 //sum is n with i = 0
b. n lg( i^2 ) //sum is n with i = 0
c. (i + 1)*2^i //sum is n with i = 0
d. (i + j) //first sum is n with i = 0 //second sum is i-1 j=0
Explanation / Answer
a)
it will be O(n^6) as it will be the biggest term in the series
b)
It will be sqrt(9n) as the function will increase more with the same
c)
It will be O(n^2) logn as the function will increase highest for this one.
d)
It will be O(n^2) for this as well.
a)
it will be i^4
b)it will be nlogn
c) it will be 2^i*i
d) it will be n
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.