n 1 (2)log 1 2. 3n 3. 4 (5) n! n n 6 log n log(n!)...

Transcribed Image Text:

n 1 (2)log 1 2. 3n 3. 4 (5) n! n n 6 log n log(n!) 22 8. 9 (10 In ln n 1 (11 12 13 (14 logn (15) n In n log log n (n+1)! (16 17 2n n log n 18 22" +1 19 5n2 (20 13n + 6 n/logn Reading the long list, Xianghu and Jordan realized that things were not as simple as they thought, and felt really upset. Could you help them with the following problems? (You don't need to explain your answer for this entire problem.) (1) (1pt) What does polynomial mean (use O(.), (.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are polynomial? (2) (1pt) What does polylogarithmic mean (use O(-), N(.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are polylogarithmic? (3) (1pt) What does sublinear mean (use O(.), N(.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are sublinear? (4) (1pt) What does superlinear mean (use O(.), (.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are superlinear? (5) (2pts) Which of the above 20 functions grow the fastest (if you think there are multiple answers, list all of them)? (6) (6pts) Finally, please rank all the functions by ascending order of growth; Group together those func- tions that are big-Theta of one another. n 1 (2)log 1 2. 3n 3. 4 (5) n! n n 6 log n log(n!) 22 8. 9 (10 In ln n 1 (11 12 13 (14 logn (15) n In n log log n (n+1)! (16 17 2n n log n 18 22" +1 19 5n2 (20 13n + 6 n/logn Reading the long list, Xianghu and Jordan realized that things were not as simple as they thought, and felt really upset. Could you help them with the following problems? (You don't need to explain your answer for this entire problem.) (1) (1pt) What does polynomial mean (use O(.), (.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are polynomial? (2) (1pt) What does polylogarithmic mean (use O(-), N(.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are polylogarithmic? (3) (1pt) What does sublinear mean (use O(.), N(.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are sublinear? (4) (1pt) What does superlinear mean (use O(.), (.), w(.), (.), o(.) to present your answer)? (2pts) Which of them are superlinear? (5) (2pts) Which of the above 20 functions grow the fastest (if you think there are multiple answers, list all of them)? (6) (6pts) Finally, please rank all the functions by ascending order of growth; Group together those func- tions that are big-Theta of one another.

Answer rating: 100% (QA)

1 Polynomial means O Omega and Theta where O represents an upper bound on the time complexity Omega ... View the full answer