Java.Collections.What is the worst case execution time of the add() method for ArrayList?

Let’s dive into the worst-case time complexity of the add() method for ArrayList.

---

✅ 1. add(element) — Add to the end

🔍 What normally happens:

• If there’s room in the internal array → element is added in O(1).
• If the internal array is full → ArrayList must:
  1. Allocate a new array (usually 1.5x bigger),
  2. Copy all existing elements to the new array,
  3. Add the new element.

---

⏱️ Worst-case time complexity:

❌ O(n) when a resize occurs
(because copying all n existing elements takes O(n))

---

✅ Amortized time:

✅ O(1) on average — because resizing doesn’t happen on every call.

---

🧠 Example:

ArrayList<Integer> list = new ArrayList<>(2);
list.add(1); // O(1)
list.add(2); // O(1)
list.add(3); // 🚨 Resize! O(n)

So:

• Most add() calls are cheap ✅
• But occasionally, one call is expensive ❌ (due to resizing)

---

🧠 Summary: ArrayList.add(element)

Case	Time Complexity
Best/Average (amortized)	✅ O(1)
Worst (on resize)	❌ O(n)

Nice follow-up, Stanley! Now let’s talk about what happens when you add to the middle or beginning of an ArrayList.

---

⚙️ What happens internally?

ArrayList stores elements in a contiguous array. When you insert into the middle or beginning, Java must:

1. Shift all elements from that index one position to the right to make room.
2. Then insert the new element.

---

⏱️ Worst-case time complexity: O(n)

• If you insert at the beginning (index = 0), it must shift all n elements.
• If you insert in the middle, it shifts roughly n/2 elements.
• Inserting at the end is usually O(1) unless resize happens.

---

🧠 Summary of add(index, element) in ArrayList:

Position	Time Complexity
Beginning (0)	❌ O(n)
Middle (n/2)	❌ O(n)
End (n)	✅ O(1) (amortized) or ❌ O(n) (if resize happens)

---

🔍 Example:

ArrayList<String> list = new ArrayList<>();
list.add("a"); // ["a"]
list.add(0, "x"); // ["x", "a"] → shifts "a" → O(n)
list.add(1, "y"); // ["x", "y", "a"] → shifts "a" → O(n)

If you’re doing a lot of insertions at the beginning or middle, use a LinkedList instead — it’s optimized for that (O(1) if you already have the position).