Question

please do all parts

a.For resizable array based implementation, what is the time complexity in the worst and base case scenario? Explain.

b. For linked implementation of a list, what is the time complexity in the wort and best case scenario? Explain.

remove(givenPosition: integer)

Answer 1

a.

In resizable array based implementation, elements are stored at the start of an underlying fixed array, and the remaining positions are unused.

• If there is room left, elements can be added at the end in constant time.
• If there is no remaining positions, the underlying fixed-sized array needs to be increased in size.

Here’s a view of the memory when appending the elements 2, 7, 1, 3, 8, 4 to an initially empty dynamic array with capacity 2.

The time to append an element is linear in the worst case, since it involves allocating new memory and copying each element.

However, if we expand the array by a constant proportion, e.g. by doubling its size, the total time to insert n elements will be O(n), and we say that each insertion takes constant amortized time.

b.for linked implementation of list we can also state as linked list

Time complexity	Space Complexity
Average	Worst	worst
Access	Search	Insertion	Deletion	access	Search	Insertion	Deletion
Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)

A linked list can typically only be accessed via its head node. From there you can only traverse from node to node until you reach the node you seek. Thus access is O(n).

Searching for a given value in a linked list similarly requires traversing all the elements until you find that value. Thus search is O(n).

Inserting into a linked list requires re-pointing the previous node (the node before the insertion point) to the inserted node, and pointing the newly-inserted node to the next node. Thus insertion is O(1).

Deleting from a linked list requires re-pointing the previous node (the node before the deleted node) to the next node (the node after the deleted node). Thus deletion is O(1).

if any other query arise do comment.