Please visit, subscribe and share 10 Minutes Lectures in Computer Science

# 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(n2) is the correct ascending order of time complexities (low to high time complexities)

(a) TRUE                                                   (b) FALSE

### 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(n2) is quadratic time. For example, bubble sort algorithm takes quadratic time to sort the elements.

2. Let f(n) = 2n2 + 5n +12. Then f(n) is O(2n).
(a) TRUE                                                   (b) FALSE

 Answer: TRUE Let us assume f(n) = 2n2 + 5n +12 and g(n) = 2n. Assuming n>1 then f(n)/g(n) = (2n2 + 5n +12)/ 2n < (2(2n)+5(2n)+12(2n))/2n = 19(2n)/2n = 19. Choose C = 19. Thus, 2n2 + 5n +12 ≤ 19*2n whenever n>1.

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

(a) TRUE                                                   (b) FALSE

The 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

### Average case running time of bubble sort is O(n2).

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(2n/4) is true for any value of n.
(a) TRUE                                                   (b) FALSE

 Answer: FALSE The 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(2n/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: FALSE The 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.

(a) TRUE                                                   (b) FALSE

 Answer: TRUE Customers 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.

(a) TRUE                                                   (b) FALSE

 Answer: FALSE A complete binary tree with a height of h have 2h−1 to 2h − 1 nodes. A complete binary tree with a height of h have 2h − 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: TRUE Dequeue 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(N3), then A1 always runs faster than A2, for any input.
(a) TRUE                                                   (b) FALSE

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

***********