retagged by
1,179 views
1 votes
1 votes

Here In this question it is given that we have to perform nlogn decrease key operation and n find operation .
1)Finding an element in the linked list itself takes O(n) and there are N such operations total=O(n2).
2)Decrease key: Find key O(n) + O(1) for decrease=O(n) and there are nlogn such operations: total O(n2logn).
Please correct Me :
Image :

retagged by

1 Answer

1 votes
1 votes

Linked List
i. root(n) insert  operations = $O(root(n))$ we can insert at the beginning of the linked list.
ii. O(nlogn) decrease key operation = as it's not given that linked is sorted, Hence, O(1) needs for one decrease key operation, total T.C needed is $O(nlogn)$.
iii. n find operations, each needs O(n), total cost $O(n^2)$

Max if these three is $O(n^2)$.

Hence, correct answer is (B).
 

Answer:

Related questions

1 votes
1 votes
1 answer
1
5 votes
5 votes
1 answer
2
hacker16 asked Nov 14, 2017
3,424 views
What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?O(n)O(1)θ(n2)θ...
3 votes
3 votes
2 answers
3
Vishal Goyal asked Sep 26, 2016
676 views
Two linked lists having n and m elements are stored in sorted order. What is the worst case complexity of program to print common elements of two lists ?$\begin{align*} &...