# Lists, sets & time complexity

Code With Purpose · English · Free starter lesson

## Concept

A list preserves order and can contain repeated values. A set holds unique, hashable values and does not promise list-like ordering. Use a list when sequence matters; use a set when you mainly need uniqueness or membership checks.

Big-O describes growth as input size n increases; it is not a stopwatch reading. Searching an unsorted list takes O(n) in the worst case. Set membership is O(1) on average under typical hashing behavior, with O(n) possible in the worst case. Building a set also costs time and memory.

If you make many membership checks, building one set may help. Rebuilding the set for every check wastes work. The code finds duplicate values and preserves the order in which each duplicate is first encountered. Its expected running time is O(n), and extra storage is O(n).

## Example

```python
def find_duplicates(values):
    seen, reported = set(), set()
    duplicates = []
    for value in values:
        if value in seen and value not in reported:
            duplicates.append(value)
            reported.add(value)
        seen.add(value)
    return duplicates

print(find_duplicates([3, 1, 3, 2, 1, 3]))
```

## Expected output

```text
[3, 1]
```

## Exercise

Write unique_in_order(values) for hashable values. Check [4, 2, 4, 1, 2]. Explain why list(set(values)) does not promise the same order.

## Suggested solution

```
def unique_in_order(values):
    seen = set()
    result = []
    for value in values:
        if value not in seen:
            result.append(value)
            seen.add(value)
    return result

print(unique_in_order([4, 2, 4, 1, 2]))  # [4, 2, 1]
# Sets do not provide a sequence-order guarantee.
```

## Takeaway

Include setup cost and memory when comparing approaches.

Reference: https://docs.python.org/3/tutorial/datastructures.html

https://codewithpurposeai.in/lesson-dsa-complexity.html?lang=english