For each of the following functions, what would the worst case running time be i

Question

For each of the following functions, what would the worst case running time be in Big O if the data structure contained n elements? the elements are not necessarily in any order. Would any of the answers change for the linked list if you keep a pointer pointing to the last element? which ones and how?

Array

Linked List

1. Print

2. Print ith element

3. Insert before the first element

4. Insert after the last element

5. Delete the first element

6. Delete the last element

Array

Linked List

1. Print

2. Print ith element

3. Insert before the first element

4. Insert after the last element

5. Delete the first element

6. Delete the last element

Explanation / Answer

First Difference Between Array and LinkList :

Both Arrays and Linked List can be used to store linear data of similar types, but they both have some advantages and disadvantages over each other.

Following are the points in favour of Linked Lists.

(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, upper limit is rarely reached.

(2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.

For example, suppose we maintain a sorted list of IDs in an array id[].

id[] = [1000, 1010, 1050, 2000, 2040, .....].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

So Linked list provides following two advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion

Linked lists have following drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
3) Arrays have better cache locality that can make a pretty big difference in performance.

Array Link List Print O(n) O(n) Print ith element O(1) O(n) if we do sequential search whereas O(logn) if we do binary search Insert Before the first Element O(n) O(1) Insert after the Last Element if Array size was equal to last element, O(n) else if array was larger than last element size , O(1) O(1) Delete the first element O(n) O(1) Delete the last element If we make array size a one less then we can do it in O(1) but if we go by rule it will take O(n) O(1)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.