CompSci 102 Discrete Mathematics for CSSpring 2005 Forbes In-class Questions 11. Given: T1(n) ∈ O(f(n)) and T2(n) ∈ O(f(n)), state which of the following statements aretrue or false and give a justification.(a) T1(n) + T2(n) ∈ O(F(n))(b) T1(n) − T2(n) ∈ O(F(n))(c) T1(n)/T2(n) ∈ O(1)(d) T1(n) ∈ O(T2(n))12. Order the following functions by growth rate. Indicate which functions grow at the same rate.n,√n, n1.5, n2, n log n, n!, n log log n, n log2n, n log(n2), 2/n, 2n, 2n/2, 37, n3, nn, n2log n3. An algorithm takes 0.5ms for input size 100. How long will it take for input size 500 if therunning time is the following? What assumptions do you have to make in order to answerthis problem?(a) O(n)(b) O(n log n)(c) O(n2)(d) O(n3)CompSci 102, Spring 2005, In-class Questions 1
View Full Document
Unlocking...