Time complexity of Data Structures

Question

I was going over this page:

And I had the following questions:

1. Does Insertion and Deletion in this table mean insertion and deletion at the end only?

2. For Basic Array, why is insertion and deletion for average and worst case marked as -?

3. What does Indexing mean in the table? Does it mean Accessing?

4. Why is Insertion and Deletion of Dynamic Array O(n)?

5. Why is the index of Linked List O(n) while that of Dynamic Array O(1)? Is it because Dynamic Array is continuous and could be accessed directly by pointer arithmetic, while for a linked list a linear search would be needed?

Answer 1

1. Does Insertion and Deletion in this table mean insertion and deletion at the end only?

   No. Those reflect random insertion and deletion.

---

2. For Basic Array, why is insertion and deletion for average and worst case marked as -?

   Because "Basic Array" is a static array structure. You cannot insert or delete elements.

---

3. What does Indexing mean in the table? Does it mean Accessing?

   It means: to access by index (position) as opposed to access by key (element value).

---

4. Why is Insertion and Deletion of Dynamic Array O(n)?

   Because insertion/deletion may require that the array grows or shrinks in length. This may involve copying (all) elements. Therefore O(N).

---

5. Why is the index of Linked List O(n) while that of Dynamic Array O(1)? Is it because Dynamic Array is continuous and could be accessed directly by pointer arithmetic, while for a linked list a linear search would be needed?

   Yes.

Answer 2

For 4, when you insert or delete an element into or from a D-array, you should indicate the index to insert or delete, so you need to make some elements moving forward or backward