Computer Science > QUESTIONS & ANSWERS > Hw 1-soln-rubric . University of Illinois . Urbana Champaign CS 466 ( Questions with complete soluti (All)

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

Reviews( 0 )

$8.00

Add to cart

Instant download

Can't find what you want? Try our AI powered Search

OR

GET ASSIGNMENT HELP
49
0

Document information


Connected school, study & course


About the document


Uploaded On

Sep 28, 2022

Number of pages

12

Written in

Seller


seller-icon
A-LEVEL GURU

Member since 2 years

17 Documents Sold


Additional information

This document has been written for:

Uploaded

Sep 28, 2022

Downloads

 0

Views

 49

Document Keyword Tags

Recommended For You

What is Browsegrades

In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Browsegrades · High quality services·