#2 Consider the following function complexities f1(n) = 5n-n+3 f(n) = 5lgn + 3 fs(n) =lg(n)...

Transcribed Image Text:

#2 Consider the following function complexities f₁1(n) = 5n²-n+3 f₂(n) = 5lgn + 3 fs(n) =lg(n²) f3(n) = 4nlgn fo(n) = en (a) List all the elements of the following Big "0" sets, given the following 5 functions. Remember that Big "O" contains proportional and slower-growing functions. All you need to do is add all appropriate fi into the sets, denoted by the { }. It is possible that a set will not have elements in it. f4(n) = 3n+ 4 O(n³) = { O(n) = { O(Ign) = { 0(3n) = { 0(n²) 0(Ign) o(nlgn) { o(3¹) = { = { } = { } (b) Do the same for the Big 0 and Little "o" sets. It is possible that a set will not have elements in it. } } } } } } (c) If Suppose f(n) is a function which belongs in sets O(n²) as well as in (n). List any 4 ▬ functions that would belong in both sets. (d) Suppose a function f(n) belongs in both O(g(n)) and (g(n)). Clearly explain why this function also must belong in 0(g(n)). #2 Consider the following function complexities f₁1(n) = 5n²-n+3 f₂(n) = 5lgn + 3 fs(n) =lg(n²) f3(n) = 4nlgn fo(n) = en (a) List all the elements of the following Big "0" sets, given the following 5 functions. Remember that Big "O" contains proportional and slower-growing functions. All you need to do is add all appropriate fi into the sets, denoted by the { }. It is possible that a set will not have elements in it. f4(n) = 3n+ 4 O(n³) = { O(n) = { O(Ign) = { 0(3n) = { 0(n²) 0(Ign) o(nlgn) { o(3¹) = { = { } = { } (b) Do the same for the Big 0 and Little "o" sets. It is possible that a set will not have elements in it. } } } } } } (c) If Suppose f(n) is a function which belongs in sets O(n²) as well as in (n). List any 4 ▬ functions that would belong in both sets. (d) Suppose a function f(n) belongs in both O(g(n)) and (g(n)). Clearly explain why this function also must belong in 0(g(n)).

Answer rating: 100% (QA)

Step 1 a List all the elements of the following Big O sets On35nn3 5lgn 3 4n lg n 3n 4 lg n e On 5nn... View the full answer