ArrayList Time Complexity: get, add, remove, contains

Direct Answer

For ArrayList, get and set are O(1); end append is amortized O(1); insertion or removal near the middle is O(n) because references shift; contains and indexOf are O(n). A particular append that grows the backing array is O(n), and clearing or removing may also null stored references as part of the work.

Code Example

import java.util.ArrayList;
import java.util.List;

public class ArrayListComplexityDemo {
    public static void main(String[] args) {
        List<String> orders = new ArrayList<>();
        orders.add("Order-1");          // amortized O(1) - write to next slot
        orders.add("Order-2");
        orders.add("Order-3");

        String second = orders.get(1);  // O(1) - direct array access

        orders.add(1, "Order-1.5");     // O(n) - shift later elements right
        // [Order-1, Order-1.5, Order-2, Order-3]

        orders.remove(1);               // O(n) - shift later elements left
        // [Order-1, Order-2, Order-3]

        boolean found = orders.contains("Order-2"); // O(n) - linear scan
        int index = orders.indexOf("Order-3");      // O(n) worst case
    }
}

Common Mistakes & Pitfalls

• Saying add is always O(1): The precise term is amortized O(1) — any single add that triggers a resize is O(n) because all elements get copied. "Amortized" means the average over many operations stays constant.
• Forgetting the shift cost: add(i, e) is not O(1). Every element from index i onward shifts right by one, which is O(n).
• Using ArrayList for repeated membership checks: Looping and calling contains each time nests an outer loop with an inner linear scan — O(n^2). Use a HashSet for expected O(1) membership when you check presence often.