What is the Time complexity for get() method in Java

The time complexity of the get(int index) method in Java does not depend on the List interface itself, but on the concrete implementation used during initialization, since each implementation relies on a different internal data structure.

1. ArrayList Initialization

List<Integer> list = new ArrayList<>();

list.add(1); // adding elements
list.get(0); // fetching element at index 0
Time Complexity: O(1)

Explanation:

• ArrayList is internally backed by a dynamic array

• Elements are stored in contiguous memory locations

• Index-based access is performed directly without traversal

 Direct array access results in constant-time complexity

2. LinkedList Initialization

List<Integer> list = new LinkedList<>();

list.add(1); // adding elements
list.get(0); // fetching element at index 0
Time Complexity: O(n)

Explanation:

• LinkedList is implemented as a doubly linked list

• Each element maintains references to the previous and next nodes

• To access a specific index, the list must traverse nodes sequentially
  (starting from the head or tail)

 Traversal is required, resulting in linear time complexity

3. Vector Initialization

List<Integer> list = new Vector<>();

list.add(1); // adding elements
list.get(0); // fetching element at index 0
Time Complexity: O(1)

Explanation:

• Vector is also backed by a dynamic array, similar to ArrayList

• Provides direct index-based access

• All methods are synchronized, which adds constant overhead but does not
  change the asymptotic time complexity

 Array-based access results in O(1) time complexity

Key Point

❌ Incorrect:

Time complexity of get() changes based on List initialization

✅ Correct:

Time complexity of get() depends on the specific List implementation
(ArrayList, LinkedList, or Vector) used during initialization.