Common data structures and complexity GATE 2015, Paper 1

There is a good question in GATE 2015, Paper 1 about common data structures and their complexity. Solving this would require a good understanding of these data structures. Here is the question (click on the image to see it better):

NOTE: This post is a part of a series on GATE previous year question analysis. You can explore other posts from this series using the navigation bar at the top.

What we need to understand

The above question mentions four operations, which have to be executed on the given data structures, the said number of times. We need to know the time complexity of these operations on these data structures to solve this problem. We also need to understand the basics of Big O notation to find the final answer.

How we will solve it

We will analyze the time complexity for each operations for these data structures. I will try to explain the intuition behind it without going into too much detail. Finally we will summarize the time complexities and pick the best data structure.

NOTE: The problem also mentions that delete and decrease key operations have a pointer provided to the record. This is important because before we can delete or decrease the key of a record, we first need to find it. Since a pointer is provided for these operations, the find itself is constant time and does not cost extra.

Unsorted Array 

An unsorted array by definition does not have any ordering, and so nothing can be assumed about the presence of elements in any position. Thus searching for an element might require looking at every element of the array. So, for an array of size n, it could require looking at all n positions. Hence find is O(n). 

Insert on an unsorted array can be done in constant time if we just append the new value at the end of the array. The problem is that we could run out of allocated space. In this case we need to reallocate array of double size and copy all the elements to the new space. This will take O(n) time, but since this has to be done only once per n inserts, the average time (amortized time) is still O(1). Hence insert is O(1).  (Read about Amortized time analysis to understand this better)

Delete will first require finding the element in the array. Since a pointer is provided, this will take O(1) time. Deleting the element itself will require shifting the elements of the array by one to fill up the space created by the deleted element. This will require n iterations. Delete will thus be O(n). 

Decrease key will require constant time for find and constant time for actual decreasing the key, since we can just reduce the value of the array element in constant time. Thus decrease key is O(1).

Min-Heap 

Finding a particular element in a Min heap is O(n), which is no better than an unsorted array. Although it might look like we can take some advantage of the structure of the heap, a little thought will reveal that, in the worst case, it will require us to look at all elements of the heap to search for an element. Hence find is O(n). 

Insert, delete and decrease key in heap are O(logn) by the very design of heap. 

Sorted Array

Since the array is sorted, we can use binary search for find, hence the find is O(logn). 

Insert now will be more costly, as we need to maintain the sorted-ness of the array. We will have to insert the element in its proper position, and then shift the remaining elements. Finding the proper place to insert will require logn time by binary search, and shifting will require n operations. Hence insert is O(n + logn) = O(n). 

Delete and decrease key will have the same process as for Unsorted array described above and hence O(n) and O(1) respectively. 

Sorted Doubly Linked List (SDLL)

This is probably the most complicated data structure of the lot. Though the linked list is sorted, we cannot take advantage of binary search. Find on SDLL will need O(n) time. 

Insert will require finding the right place to insert (since it is sorted), which will require n iterations in the worst case. Hence insert would be O(n).

Delete and decrease key will require constant time to search and constant time to carry out the respective operation. 

Final Answer

Based on the number of times each operation is performed in the question, the final time complexity with each data structure is:

Data Structure	Find (logn)1/2	Insert n	Delete (logn)1/2	Decrease Key (logn)1/2	Total
Unsorted Array	n * (logn)1/2	1 * n	n * (logn)1/2	1 * (logn)1/2	n * (logn)1/2
Sorted Array	logn * (logn)1/2	n * n	n * (logn)1/2	1 * (logn)1/2	n * n
Min Heap	n * (logn)1/2	logn * n	logn * (logn)1/2	logn * (logn)1/2	n * logn
SDLL	n * (logn)1/2	n * n	1 * (logn)1/2	1 * (logn)1/2	n * n