# TRUE/FALSE Quiz Questions with Answers in time complexities Data Structures and Algorithms

__Data Structures and Algorithms TRUE / FALSE Questions – Set 02__

*1. O(1), O(n), O(nlog n), O(n*^{2}) is the correct ascending order of time complexities (low to high time complexities)
(a)
TRUE (b)
FALSE

Answer:
TRUE##
Time
complexity is one of the measures to calculate the performance of an
algorithm or program.O(1)
is constant time. It takes constant amount of time. For example, to access
any particular element in an array of any size would take same amount of
time).O(n)
denotes linear time. Here, the running time grows linearly with the size of
input. For example, time required to sum n numbers grows along with n.O(n
log n) denotes linearithmic time. O(n^{2})
is quadratic time. For example, bubble sort algorithm takes quadratic time to
sort the elements. |

*2. Let f(n) = 2n*^{2}+ 5n +12. Then f(n) is O(2^{n}).
(a)
TRUE (b)
FALSE

Answer:
TRUELet
us assume f(n) = 2n^{2} + 5n +12 and g(n) = 2^{n}. Assuming
n>1 thenf(n)/g(n)
= (2n^{2} + 5n +12)/ 2^{n} < (2(2^{n})+5(2^{n})+12(2^{n}))/2^{n}
= 19(2^{n})/2^{n} = 19.Choose
C = 19. Thus, 2n^{2} + 5n +12 ≤ 19*2^{n} whenever n>1. |

###
*3. Queue and Stack are the linear data structures*

*3. Queue and Stack are the linear data structures*
(a)
TRUE (b)
FALSE

Answer:
TRUEThe
data structure where data items are organized sequentially or linearly where
data elements attached one after another is called linear data structure. In
linear data structure, each element can be traversed one after the other.Queue
is FIFO, where the first element that enters the queue will be accessed first
then the next, and so on. Stack is LIFO, where the last element inserted will
be accessed first then the next last and so on. In both of these cases,
elements are accessed one after the other in a linear or sequential order.##
Other
linear data structures are array and linked list. |

*4. Average case running time of Bubble sort is O(n log n).*
(a)
TRUE (b)
FALSE

Answer:
FALSE##
Average
case running time of bubble sort is O(n^{2}).Bubble
sort compares the adjacent elements in a list and swap them if they are in a
wrong order in its first pass. It does this continuously in consequent passes
until the all the elements in the list gets sorted. |

*5. O(n2) ≥ O(2*^{n/4}) is true for any value of n.
(a)
TRUE (b)
FALSE

Answer:
FALSEThe
given comparison is not always true. For certain values of n it is true; for
others it is not.If
n ≤ 8, then it is true. For other values of n (n > 8), O(2^{n/4})
is larger. |

*6. The tightest bound time complexity of function T(N) = T(N/2) + 100 is O(N)*
(a)
TRUE (b)
FALSE

Answer:
FALSEThe
tightest bound time complexity for the given function is O(log N). This is
less complex than O(N). |

###
*7. Queue is the suitable data structure for the application that
tracks the customer orders in an ice cream parlor.*

*7. Queue is the suitable data structure for the application that tracks the customer orders in an ice cream parlor.*
(a)
TRUE (b)
FALSE

Answer:
TRUECustomers
orders should be handled in a First In First Out (FIFO) manner. |

###
*8. A complete binary tree with a height of h can have more nodes
than a full binary tree with a height of h.*

*8. A complete binary tree with a height of h can have more nodes than a full binary tree with a height of h.*
(a)
TRUE (b)
FALSE

Answer:
FALSEA
complete binary tree with a height of h have 2^{h−1} to 2^{h}
− 1 nodes.A
complete binary tree with a height of h have 2^{h} − 1 nodes. |

*9. O(1) is the worst case time complexity of dequeue in a queue containing M elements implemented using an array.*
(a)
TRUE (b)
FALSE

Answer:
TRUEDequeue
is an operation that get the elements out of a queue. This operation can be
done on the element that is currently at the front of the queue. Hence, the complexity
is O(1). |

*10. If we have two algorithms A1 and A2, and A1 takes time O(N) while A2 is O(N*^{3}), then A1 always runs faster than A2, for any input.
(a)
TRUE (b)
FALSE

Answer:
FALSEFor
very large N, A1 will be faster than A2, but perhaps not for smaller N. |

***************

###
**Related links:**

**Related links:**

## No comments:

## Post a Comment