Time complexity of Data Structures

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

    No. Those reflect random insertion and deletion.


  1. 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.


  1. 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).


  1. 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).


  1. 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.