1. Use Big-O analysis to determine the time complexity of the following code fragment in terms of the integer n: (5 Mark

[answerhappygod]

1 Use Big O Analysis To Determine The Time Complexity Of The Following Code Fragment In Terms Of The Integer N 5 Mark 1 (253.82 KiB) Viewed 57 times

1. Use Big-O analysis to determine the time complexity of the following code fragment in terms of the integer n: (5 Marks ) a) for (k = 0; k<n/2; ++k) { } for (j = 0; j<n*n; ++i) { } Answer: (0.5 Mark) b) k= n; while (k > 1) { (0.5 Mark) k/= 2; } Answer: c) int a = 0, b = 0; for (i = 0; i < N;i++) { a = a + rand(); } for (i = 0; j < 100; j++) { b = b + rand(); } Answer: (1 Mark) d) int a = 0; for (i = 0; i < N;i++) { for(j = N; j>i; j--) { a= a +i+j; } Answer: (1 Mark) e) int foo(20) { int cost; for (int i = 0; i < 20; ++i) cost = cost+ (i * 20); return cost; } Answer: (1 Mark) it requires. 1. An algorithm's execution time is related to the number of a) parameters b) test data sets c) data fields d) operations 2. Which of the following can be used to compare two algorithms? a) growth rates of the two algorithms b) implementations of the two algorithms c) test data used to test programs which implement the two algorithms d) computers on which programs which implement the two algorithms are ru Answer: 3. Algorithm efficiency is typically a concern for a) small problems only b) large problems only c) medium sized problems only d) problems of all sizes Answer: 4. The value of which of the following growth-rate functions grows the fastest? a) O(n) b) O(n) c) O(1) d) O(login) Answer: 5. The value of which of the following growth-rate functions grows the slowest? a) O(n) b) c) O(1) d) O(logan) Answer: 6. Which of the following growth-rate functions indicates a problem whose time requirement is independent of the size of the problem? a) O(n) b) O(logan) c) (2) d) O(1) Answer: 7. A linear algorithm has the growth-rate function a) O(login) b) O(2") c) C(n) d) O(1) Answer: 8. A quadratic algorithm has the growth-rate function a) O(n) b) O(n) c) O(2") d) O(logan) Answer: 9. An exponential algorithm has the growth-rate function a) O(n) b) O(n) c) O(2") d) O(logan) Answer: 10. In the worst case, a binary search is a) O(n) b) 0(1) c) O(login) d) C(n) Answer: