Answer is (C).
- Delete $O(1)$
- Insert $O(N)$
- Find $O(N)$
Decrease Key $\Rightarrow O(N)$ //Because we need to search position in Linked list. (It is similar to a Delete followed by an Insert with the decreased value)
- $O(n)$ delete $\Rightarrow O(N \times 1 ) =O(N)$
- $O(\log N)$ find $\Rightarrow O(\log N \times N ) = O(N \log N)$
- $O(\log N)$ insert $\Rightarrow O(N \log N)$
- $O(N)$ decrease key $\Rightarrow O(N\times N) = O(N^2)$
Even though it says at start we got $N$ elements, then we are deleting $Q(N)$ elements, here $Q(N)$ can be anything like $N/2,N/4,N/3$ and list need not be empty, then above explanation holds !
In case it actually deleted all elements at start analysis will be something like below $\Rightarrow$
All $N$ elements are deleted, Time complexity $O(1)$ each delete, total delete $O(N)$
Now $\log N$ insert, it'll take $1 + 2 + \log N$ time, then ($\log N * \log N-1)/2 \Rightarrow O((\log N)^2)$
Now $\log N$ finds $\Rightarrow$ it'll take $\log N$ time per find (because find take $O(N)$ but here $N = \log N$)
$\Rightarrow O((\log N)^2)$
Now $N$ decrease key, Size of list is $\log N$, each decrease key can take $O(size \ of \ list)$
So, size of list * no. of decrease key $\Rightarrow N \times \log N = O(N \log N)$
There is no option like $O(N \log N)$
So, correct answer is $O(N^2)$.