CS466: Introduction to Bioinformatics

CS466: Introduction to Bioinformatics

Document Content and Description Below

CS466: Introduction to Bioinformatics1. 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 l... og(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]