# Library Call Costs in Practice — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/d-library

> Recognise hidden costs in common Python and Java library operations.

## Library calls have complexity too

Clean code often hides loops inside library calls. In **Python**: `x in list` is O(n) but `x in set` is O(1) average; `list.index`, `list.remove`, `list.count` and `min`/`max` are O(n); `list.insert(0, x)` and `pop(0)` are O(n); slicing `a[i:j]` copies j − i elements; `sorted()` and `list.sort()` use **Timsort**, O(n log n) worst case and very fast on partly sorted data; `heapq.heappush` is O(log n); `len()` is O(1). Repeated string concatenation in a loop can be **O(n²)** because strings are immutable; build a list and `''.join()` it. In **Java**: `ArrayList.get` is O(1) and `add` amortised O(1), but `remove(0)` is O(n); `LinkedList.get(i)` is O(n); `HashMap.get` is O(1) average; `TreeMap.get` is O(log n); `String +=` in loops creates new strings each time, so use `StringBuilder`; `Collections.sort` and `List.sort` are O(n log n). Knowing these costs prevents accidentally quadratic code that looks perfectly innocent.

## Accidentally quadratic code and its fixes

Each pair does the same job with very different growth.

```python
# 1. membership test in a list inside a loop: O(n * m)
banned = load_banned_ids()            # list of m ids
clean = [u for u in users if u.id not in banned]
# fix: O(n + m)
banned_set = set(banned)
clean = [u for u in users if u.id not in banned_set]

# 2. string building: can be O(n^2) because each += may copy the whole string
report = ""
for line in lines:
    report += line + "\n"
# fix: O(n)
report = "\n".join(lines) + "\n"

# 3. queue with a list: O(n^2) for n items
queue = list(tasks)
while queue:
    task = queue.pop(0)
# fix: O(n)
from collections import deque
queue = deque(tasks)
while queue:
    task = queue.popleft()
```

## Read the documentation's complexity notes

Python's wiki page on time complexity and the Java collections documentation list the costs of standard operations. A minute there saves hours of debugging a slow endpoint.

**Quiz:** What is the cost of `x in my_list` for a Python list of n elements?

- [x] O(n)
- [ ] O(1)
- [ ] O(log n)
- [ ] O(n log n)

*Answer:* O(n). Membership in a list is a linear scan; use a set for average O(1) membership tests.