Suppose we have a O(n) time algorithm that finds median of an unsorted array.Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.(A) O(n^2 Logn)(B) O(n^2)(C) O(n Logn Logn)(D) O(nLogn)

Suppose we have a O(n) time algorithm that finds median of an unsorted

1.	Suppose we have a O(n) time algorithm that finds median of an unsorted array.Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.(A) O(n^2 Logn)(B) O(n^2)(C) O(n Logn Logn)(D) O(nLogn)
Answer»

Discussion

No Comment Found

Related InterviewSolutions

Consider the following grammar.S -> S * ES -> EE -> F + EE -> FF -> idConsider the following LR(0) items corresponding to the grammar above.(i) S -> S * .E(ii) E -> F. + E(iii) E -> F + .E Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?(A) (i) and (ii)(B) (ii) and (iii)(C) (i) and (iii)(D) None of the above
Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is: (GATE CS 2006)(A) n — 1(B) 2n — 2(C) nC2(D) 2
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:(A) Queue(B) Stack(C) Heap(D) B-Tree
A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?(A) 400(B) 500(C) 600(D) 700
In a binary max heap containing n numbers, the smallest element can be found in time(A) O(n)(B) O(Logn)(C) O(LogLogn)(D) O(1)
You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°?(A) A(B) B(C) C(D) D
Which one of the following in place sorting algorithms needs the minimum number of swaps?(A) Quick sort(B) Insertion sort(C) Selection sort(D) Heap sort
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.(A) log2n(B) n(C) 2n + 1(D) 2^n — 1
Consider the following C-program fragment in which i, j and n are integer variables.for (i = n, j = 0; i >0; i /= 2, j += i);Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?(A) val(j) = (logn)(B) vaI(j) = (sqrt(n))(C) val(j) = (n)(D) val(j) = (nlogn)(A) A(B) B(C) C(D) D
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?(A) R is NP-complete(B) R is NP-hard(C) Q is NP-complete(D) Q is NP-hard

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment