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
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(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
Answer:
TRUE
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
Answer:
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.
|
***********
No comments:
Post a Comment