(a) Organize the following functions into six groups (labeled 1 to 6). Items in the same group should have the same asymptotic growth rates (they should be big-O of each other). If a group’s label is lower than that of another group, all its growth rates should be slower than those of the group with the larger label (so group 1 should have the slowest growth rates and group 6 should have the fastest growth rates). 20n, log3(3n), (n^3)/2, 2nlog2(n), 2n^2 + 50n, n! + n^0.5, n^5/n^2 , log3(n^4), 2^log2(n), n!/3! (b) Using the definition of big-O, show 7(n^2) + 3n = O(n^2): Give a particular C and n0 and show why these constants work. (c) Identify a function f(n) for which 8nlog4(n) + (n^2)/3 + 3(n^3) = O(f (n)). You do not need to show constants but should describe how you determined your solution.
(a) Organize the following functions into six groups (labeled 1 to 6). Items in the same group should have the same asymptotic growth rates (they should be big-O of each other). If a group’s label is lower than that of another group, all its growth rates should be slower than those of the group with the larger label (so group 1 should have the slowest growth rates and group 6 should have the fastest growth rates).
20n, log3(3n), (n^3)/2, 2nlog2(n), 2n^2 + 50n, n! + n^0.5, n^5/n^2 , log3(n^4), 2^log2(n), n!/3!
(b) Using the definition of big-O, show 7(n^2) + 3n = O(n^2): Give a particular C and n0 and show why these constants work.
(c) Identify a function f(n) for which 8nlog4(n) + (n^2)/3 + 3(n^3) = O(f (n)). You do not need to show constants but should describe how you determined your solution.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
