Question

Basic Algorithm Analysis:

1 a. What is the time complexity to get an item from a specific index in an ArrayList?
b. What is the time complexity remove an item in the middle of an ArrayList and why?
c.What is the average time complexity to add an item to the end of an ArrayList?
d.What is the worst case time complexity to add an item to the end of an ArrayList? What if you have to or don’t have to reallocate?
e.Taking this all into account, what situations would an ArrayList be the appropriate data structure for storing your data?

Answer 1

1. a)   time complexity to get an item from a specific index in an ArrayList is O(1).

b) time complexity will be O(n),  if we want to remove an element from the middle then in the worst case we have to move all elements in the list.

c)average time complexity to add an item to the end of an ArrayList is O(1). Adding elements from the end is efficient since this is reduced to an increment or decrement of the length variable.

d)worst case time complexity to add an item to the end of an ArrayList without having to reallocate is O(1) but if we have to reallocate then it is O(n).

e)ArrayList is best when using direct reference(i.e item from the specific index) for all element, so we could get the element in constant time