Data Structure and Algorithm Analysis Set 27

Data Structure and Algorithm Analysis

Questions 261 to 270

 261 Which of the following formulas in Omega notation best represent the expression n²+35n+6? (a)  Ω (n³)                (b)  Ω (n²)                (c)  Ω (n)                 (d)  Ω (35)               (e)  Ω (6). 262 What term is used to describe an O(n) algorithm? (a)  Constant                                          (b)  Non Polynomial Deterministic           (c)  Logarithmic                                      (d)  Quadratic                                        (e)  Linear. 263 Express the formula (n - 2)*(n - 4) using θ notation: (a)  θ (n2)                 (b)  θ (8)                  (c)  θ (log n)            (d)  θ (n)                  (e)  θ (1). 264 Read the following statements carefully and pick the right most option. I.     A linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem. II.     An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10. (a)   Both (I) and (II) are TRUE    (b)   Both (I) and (II) are FALSE (c)   Only (I) is true but (II) depends upon the instance size. (d)   (I) is TRUE but (II) is FALSE            (e)   (I) is FALSE and (II) is TRUE. 265 Which of the following are essential statement types for describing algorithms? (a)  Sequence                                        (b)  Selection           (c)  Repetition (d)  All the above                                   (e)  A and B only. 266 When we say an algorithm has a time complexity of O (n), what does it mean? (a)   The algorithm has ‘n’ nested loops (b)   The computation time taken by the algorithm is proportional to n (c)   The algorithm is ‘n’ times slower than a standard algorithm (d)   There are ‘n’ number of statements in the algorithm (e)   The computation time taken by the algorithm is less than ‘n’ seconds. 267 Can we read a data item at any location of a list within a constant time (i.e. O(1))? (a)   Yes (b)   Yes, only if the list is implemented by pointers (i.e. linked-list) (c)   Yes, only if the list is implemented by an array (d)   No, we need O(n) computation steps no matter what kind of implementation is used (e)   No, as constant time is not possible for algorithms. 268 Sequential search has a time complexity of O(n), and binary search has a time complexity of O(log(n)). What difference will it make when the size n is 1000? (a)   You would not notice much difference because computers run very fast anyway (b)   As n is 1000, binary search is twice as fast as sequential search (c)   As n is 1000, binary search is 10 times as fast as sequential search (d)   As n is 1000, binary search is 10 times as slow as sequential search (e)   As n is 1000, binary search is 100 times as fast as sequential search. 269 Read the following statements carefully, and choose the correct answer. I.     The Ω notation is Anti Symmetric. II.     The big Oh notation is Semi Equivalence. (a)  (I) is FALSE but (II) is TRUE              (b)  Both (I), (II) are TRUE (c)  (I) is TRUE but (II) is FALSE              (d)  Both (I), (II) are FALSE (e)  (II) is TRUE and (I) cannot be defined. 270 Find the odd one out. (a)  Bin-Packing Problem                        (b)  TVSP Problem                    (c)  Knap Sack Problem (d)  OBST Problem                                (e)  Sum of Sub Sets Problem.