Are these time complexities correct

Question

I wanted to know if my time complexities regarding the following points along with the reasoning are correct or not.

1. Insertion at the end of a dynamic array is O(1) and anywhere else in O(n) (since elements might need to copied and moved) (resembling a std::vector)
2. Searching through a single link list is O(n) since its linear.
3. Insertion and deletion in a single link list could either be O(1) or O(n). It is O(1) if the address to the node is available otherwise its O(n) since a linear search would be required.

I would appreciate feedback on this

Answer 1

Insertion at the end of a dynamic array is O(1) and anywhere else in O(n) (since elements might >need to copied and moved) (resembling a std::vector)

Amortized time complexity of a dynamic array is O(1). https://stackoverflow.com/a/249695/1866301

Searching through a single link list is O(n) since its linear.

Yes

Insertion and deletion in a single link list could either be O(1) or O(n). It is O(1) if the address to the node is available otherwise its O(n) since a linear search would be required.

Yes, if the nodes of the linked list are indexed by their addresses, you could get O(1), else you will have to search through the list which is O(n). There are other variants like skip list for which search is logarithmic, O(log n). http://en.wikipedia.org/wiki/Skip_list

Answer 2

1) Insertion at the end of a dynamic array is amortized O(1). The reason is that, if the insertion forces a reallocation, the existing elements need to be moved to a new block of memory which is O(n). If you make sure the array is grown by a constant factor every time an allocation occurs, eventually the moves become infrequent enough to become insignificant. Inserting into the middle of a dynamic array will be O(n) to shift the elements after the insertion point over.

2) Correct; searching through a linked list, sorted or not, is O(n) because each element of the linked list will be visited during the search.

3) This is also correct. If you don't need a sorted list, insertion into a singly linked list is usually implemented as adding to the head of the list, so you can just update the list head to the new node and the next pointer of the new node to the be the old head of the list. This means insertion into an unsorted singly linked list will often be indicated as O(1) without much discussion.

Answer 3

Take a look at this cheatsheet for algorithm complexity, I use it as a reference