DSA in DartEasy20 XP3 min read
What are the time complexities of common Dart List operations?
TL;DR: List: O(1) access by index/add at end, O(n) insert/remove at front/middle, O(n) contains(). Set/Map (HashMap-backed): O(1) average for add, remove, contains. SplayTreeSet/Map: O(log n) all operations but sorted.
Full Answer
Dart List (dynamic array)
- ▸list[i]: O(1) — direct index access
- ▸list.add(x): Amortized O(1) — doubles capacity when full
- ▸list.insert(0, x): O(n) — shifts all elements right
- ▸list.remove(x): O(n) — linear scan + shift
- ▸list.contains(x): O(n) — linear scan
- ▸list.sort(): O(n log n) — TimSort
Dart Set/Map (HashSet/HashMap)
- ▸set.add(x) / map[k] = v: O(1) average, O(n) worst (hash collision)
- ▸set.contains(x) / map[k]: O(1) average
- ▸set.remove(x): O(1) average
Code Examples
dartO(n²) vs O(n) with right collection
Output
// 10,000 questions: O(n²) = 100,000,000 ops vs O(n) = 10,000 ops
Common Mistakes
- ✗list.first / list.last on an empty list — throws StateError, use firstOrNull from collection package
- ✗Calling list.sort() inside a build() method — expensive and runs on every rebuild
Interview Tip
💡
The O(n²) List.contains()-in-loop vs O(n) Set pattern is the most commonly asked optimization in Flutter interviews. Know it cold.
#big-o#time-complexity#list#dart-collections