Hw 1-soln-rubric . University of Illinois . Urbana Champaign CS 466 ( Questions with complete solution)

Document Content and Description Below

Hw 1-soln-rubric . University of Illinois . Urbana Champaign CS 466 ( Questions with complete solution)Instructions: This homework assignment consists of five questions worth a total of 50 points. In... addition, there is a bonus question on the third page worth an additional 6 points. These questions are based on the material covered in Lectures 1 to 5. Do not forget to write your name at the top! 1. Asymptotic Running Time [5 points] Consider the following running time functions, where n > 0. n2 n3 pn n2 log(n) n log(n) n! 2n n n(n + 1) − n2 n + n2 n log(n2) n3 − n2 1 n2 − n nn 10,000,000 a. Identify groups of functions such that for any pair (f(n); g(n)) of functions in the same group it holds that both f(n) = O(g(n)) and g(n) = O(f(n)). Note that some groups will contain a single function. [3 points] Hint: For example, f(n) = 3n and g(n) = n would be in the same group, as f(n) = 3n = O(n) = O(g(n)) and g(n) = n = O(3n) = O(f(n)). Group 1: 1; 10,000,000 O(1) Group 2: pn O(pn) Group 3: n; n(n + 1) − n2 O(n) Group 4: n log(n); n log(n2) O(n log n) Group 5: n2; n + n2; n2 − n O(n2) Group 6: n2 log(n) O(n2 log n) Group 7: n3; n3 − n2 O(n3) Group 8: 2n O(2n) Group 9: n! O(n!) Group 10: nn O(nn) b. Arrange the resulting Big Oh running time groups in order from fastest to slowest. [2 points] Group 1 ⊂ : : : ⊂ Group 10. Rubric: • -0.5 for wrong groups. • -0.5 for each missing group or each additional group. • -0.5 for each wrongly ordered group in part b. Do not consider excess or missing groups here. [Show More]

Last updated: 1 year ago

Preview 1 out of 12 pages