Question

Compare the worst case run time complexity of the below functions in Unsorted arrays, sorted arrays and linked lists(unsorted) (15 points).

• a) Find (given an element, return the index)
• b) Insert (given an element, insert it)
• c) Delete (given an element, find it then delete it)

Answer 1

a) Find (given an element, return the index)

Unsorted Array: In unsorted array given an element, finding it's location takes O(n) in the worst case. This is because in the worst case the element we want to find may present at the end of an array.

Sorted array: It takes O(log n) time. Since the array is sorted, we can use binary search to find location of an element which takes O(log n) in worst case.

Linked list(Unsorted): It takes O(n) time. In the worst case the element we are looking art may present at the end of the linked list and hence we need to traverse entire linked list which takes O(n) time.

b) Insert (given an element, insert it)

Unsorted Array: It takes O(1) time. array is unsorted, so insertion can be done at end of array which takes O(1) time.

Sorted array: Worst case time complexity of it is O(n) time. Since the array is sorted, to find it's appropriate location to insert it takes O(log n) and to insert we may have to shift all other element to it's right in worst case, which takes O(n) time. so total time complexity is equal to O(n+log n) which is equal to O(n).

Unsorted Linked list:

Case(i): If reference to start of the linked list is given: Then it takes O(n) time to insert. This is because iterator has to traverse from head to the end of the list to insert an element

Case(ii): If reference to location of element we want insert is given: Then it takes O(1) time.

c) Delete (given an element, find it then delete it)

Unsorted Array: It takes O(n) time. To find an element it takes O(n) time for finding and O(n) for deletion. (i.e, deletion may happen in the beginning and all the elements have to shifted to their left by one place). So total time is O(n+n) = O(n).

Sorted array: Worst case time complexity of it is O(n) time. It takes O(log n) time for finding and O(n) for deletion. (i.e, deletion may happen in the beginning and all the elements have to shifted to their left by one place). So total time is O(log n+n) = O(n).

Unsorted Linked list:

If reference to start of the linked list is given: Then it takes O(n) time to delete. This is because iterator has to traverse from head to location of an element which takes O(n) in the worst case and for deletion it takes O(1) to delete it. Total time it takes is O(n+1) = O(n).

If the reference to the position of element we want delete is given it takes O(1) time.

Summary Table:

	Find	Insert	Delete(finding and then delete)
Unsorted Array	O(n)	O(1)	O(n)
Sorted Array	O(log n)	O(n)	O(n)
Unsorted Linked list	O(n)	O(n) or O(1)*	O(n)

* indicates that it takes O(1) time to insert if pointer to the location where new element needs to be inserted is given, else it has to traverse from head to the end of list which takes O(n) time.