Test: Asymptotic Analysis of Algorithms- 2 - Computer Science Engineering (CSE) MCQ

Randomized quicksort has expected time complexity as O(nLogn), but worst case time complexity remains same. In worst case the randomized function can pick the index of corner element every time.

In worst case, the chosen pivot is always placed at a corner position and recursive call is made for following. a) for subarray on left of pivot which is of size n-1 in worst case. b) for subarray on right of pivot which is of size 0 in worst case.

We only need to consider any 3 elements and compare them. So the number of comparisons is constants, that makes time complexity as Θ(1) The catch here is, we need to return any element that is neither maximum not minimum. Let us take an array {10, 20, 15, 7, 90}. Output can be 10 or 15 or 20 Pick any three elements from given liar. Let the three elements be 10, 20 and 7. Using 3 comparisons, we can find that the middle element is 10.

A problem in NP becomes NPC if all NP problems can be reduced to it in polynomial time. This is same as reducing any of the NPC problem to it. 3-SAT being an NPC problem, reducing it to a NP problem would mean that NP problem is NPC.

A set of vertices is called independent set such that no two vertices in the set are adjacent. A maximal independent set (MIS) is an independent set which is not subset of any other independent set. The question is about smallest MIS. We can see in below diagram, the three highlighted vertices (2nd, 5th and 8th) form a maximal independent set (not subset of any other MIS) and smallest MIS.
0----0----0----0----0----0----0----0----0

Radix sort time complexity = O(wn)
for n keys of word size= w
⇒w = log(n^k)
O(wn)=O(klogn.n)
⇒ kO(nlogn)

The term O(1) states that the space required by the insertion sort is constant i.e., space required doesn't depend on input.

When we have 'i' numbers stored in an array, we have to swap all positive numbers with negative and in worst case positive numbers will be i/2.

Using optimal merge pattern algorithm arrange files in increasing order of records:
D  A   C     B   E

5  10  15   20  25 

Now, minimum number of record movements required = sum of internal node's value = 15 + 30 + 45 + 75 = 165 So, option (A) is correct.

In first pass the elements are sorted in n/4 (first 2 elements in each group) sub arrays but in second pass the elements are sorted in n/2 (first 4 elements in each group) sub arrays.

Trial (a,b,c) return the median element of the a, b and c,but not middle element of a , b and c. But if a = b = c, then infinite loop. So, Option (D) is correct.

The above program doesn’t work for the cases where element to be searched is the last element of a[] or greater than the last element (or maximum element) in a[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

Correct matching is A – 3, B – 2, C – 4, D – 1. Option (A) is correct.

The outer loop runs n/2 times The inner loop runs logn times Therefore the total time complexity of the program is O(nlogn) which is option (D)

In binary tree branching factor is 2 and space complexity for height n is O(2ⁿ).
In ternary tree branching factor is 3 and space complexity for height n is O(3ⁿ).
Similarly
If branching factor is b and height is m for search tree then space complexity of greedy search is O(b^m).
So, option (C) is correct.

Transitive closure generally uses Floyd-Warshall Algorithm which gives a time complexity of O(n³)

According to given question:
h(4) = 88
88 = 2 h(3) + 4 h(2)
= 2 [2 h(2) + 4 h(1)] + 4 h(2)
= 8 h(2) + 8 h(1)
= 8 (2 + 4 k) + 8
= 24 + 32 k
 i.e.   k = 2
So, option (C) is corrct.

1. Merge sort is a Divide and conquer algorithm
2. Huffman coding is a Greedy approach
3. Optimal polygon triangulation is Dynamic programming algorithm
4. Subset sum problem is a Back tracking algorithm

So, option (D) is correct.

1. Prim’s algorithm takes O(E lgV) time.
2. Bellman-Ford algorithm takes O(V2E) time.
3. Floyd-Warshall algorithm takes O(V3) time.
4. Johnson’s algorithm takes O(VE lgV) time.

So, option (C) is correct.

• Huffman codes takes O(nlgn) time.
• Optimal polygon triangulation takes θ(n³) time
• Activity selection problem takes θ(n) time
• Quicksort takes O(n²) time

So, option (C) is correct.