Linked List problem gate 2016


#1

Please explain the solution in Layman Term


#2

Just remember 1 important property to solve this type of problems.

θ(N) <= O(N)

Now in given question it is said that we are to perform,
θ(N) delete operations
O(log N) insert operations
O(log N) find operations
θ(N) Decrease-Key Operations

Refer to the link below and see the worst case time complexity of delete, insert and find operations for doubly linked list.
http://bigocheatsheet.com/

Now let’s calculate time complexity of all the operations,

= (No. of delete operations)(Time taken for each delete operation) + (No. of insert operations)(Time Taken for each insert operation) + (No. of find operations)(Time taken for each find operation) + (No. of decrease_Key operations)(Time Taken for each decrease_key operation)

= θ(N)θ(1) + O(log N)O(N) + O(log N)O(N) + θ(N)O(N)

= O(N)O(1) + O(log N)O(N) + O(log N)O(N) + O(N)O(N) { using the property θ(N)<=O(N) }

= O(N) + O(Nlog N) + O(NlogN) + O(N^2)

=O(N^2)

This is the tightest upper bound to the problem…

You might get a doubt that why ‘Time Taken For Each decrease_Key operation is of the order O(N) even if a pointer is provided to the record on which decrease_Key is to be applied

The answer for this is, after you decrease the key, the array needs to remain sorted. So in worst case suppose you made the largest element as the smallest element then you have to move it to the 1st place. So it would be O(N).


#3

Cant we use binary search for find operartion since it is a sorted doubly linked list