N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together

N items are stored in a sorted doubly linked list. For a delete operat

1.	N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together
A.	O(Log2N)
B.	O(N)
C.	O(N2)
D.	Θ(N2 Log N)
Answer» D. Θ(N2 Log N)

Discussion

No Comment Found

Related MCQs

Consider a 128×10 3 bits/second satellite communication link with one way propagation delay of 150 milliseconds. Selective retransmission (repeat) protocol is used on this link to send data with a frame size of 1 kilobyte. Neglect the transmission time of acknowledgement. The minimum number of bits required for the sequence number field to achieve 100% utilization is ___________
For the IEEE 802.11 MAC protocol for wireless communication, which of the following statements is/are TRUE? <pre> I. At least three non-overlapping channels are available for transmissions. II. The RTS-CTS mechanism is used for collision detection. III. Unicast frames are ACKed.</pre>
A network has a data transmission bandwidth of 20 × 10 6 bits per second. It uses CSMA/CD in the MAC layer. The maximum signal propagation time from one node to another node is 40 microseconds. The minimum size of a frame in the network is _________ bytes.   Note : This question was asked as Numerical Answer Type.
where ri(Z) denotes a read operation by transaction Ti on a variable Z, wi(Z) denotes a write operation by Ti on a variable Z and ai denotes an abort by transaction Ti . Which one of the following statements about the above schedule is TRUE?
The smallest cache size required to ensure an average read latency of less than 6 ms is _______ MB
Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is ________.
Consider the following two-process synchronization solution. <pre> Process 0 Process 1 Entry: loop while (turn == 1); Entry: loop while (turn == 0); (critical section) (critical section) Exit: turn = 1; Exit turn = 0; </pre> The shared variable turn is initialized to zero. Which one of the following is TRUE?
A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, <pre> int a[10][3]; </pre> The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num. <pre> Grammar G1 D → int L; L → id [E E → num] E → num] [E Grammar G2 D → int L; L → id E E → E[num] E → [num] </pre> Which of the grammars correctly generate the declaration mentioned above?
Consider the following languages. <pre> L1 = { <M> | M takes at least 2016 steps on some input}, L2 = { <M> | M takes at least 2016 steps on all inputs} and L3 = { <M> | M accepts ε},</pre> where for each Turing machine M,   <M> denotes a specific encoding of M. Which one of the following is TRUE?
Consider the following languages: L1 = {anbmcn : m, n >= 1} L2 = {anbnc2n : n >= 1} Which one of the following is TRUE?

Discussion

No Comment Found

Related MCQs

Reply to Comment