# 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.

Answers:

 261 Answer : (b) Reason:  As the given expression is a quadratic equation of degree 2, then by ignoring the constants and lower order terms, the highest term is n2, and hence it is Ω(n2). 262 Answer : (e) Reason:  Because it is a single term of degree one. And all the remaining options are wrong. 263 Answer : (a) Reason:  Again this is a polynomial of degree 2 i.e. n2 – 6n + 8. And hence n2 according to above reason of Question (21). 264 Answer : (d) Reason:  As the first statement is true according to the definition of linear algorithms, the second is false as 30 operations are not needed. 265 Answer : (d) Reason:  Because all are essential for the algorithm to state the solution of a given problem. 266 Answer : (b) Reason:  As all the other options are meaning less and are wrong. 267 Answer : (c) Reason:  For an array implementation, we can find the given location straightway with the index value and hence it takes constant time. But for a linked list, we have to follow the pointers one by one. The cost of this is proportional to the size of the list. 268 Answer : (e) Reason:  log(1024) = 10,  1000/log(1000) is roughly equal to 1000/10 = 100 269 Answer : (b) Reason:  According to the definitions of Omega, Big Oh notations. 270 Answer : (a) Reason:  As Bin-Packing problem belongs to NP ( Non Deterministic Polynomial) hard problems and the remaining all are Deterministic polynomial time algorithms.

<< PrevNext >>

#### 2 comments :

1. 2. 