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 :
It is asking for asymptotic complexity
So, maximum of all 3 operation is nlogn
So, O(nlogn) or O(n2) fine for answer
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).
manu for decrese key you need to search the list it will take O(n2logn)
it's an implicit thing, decrease_key operation always meant to decrease the key of a node which will be passed as a parameter./
Anyway, I am sending you the following decrease key procedure from Heap-sort patr from Coreman: