Mekkora az időbeli komplexitása egy elem keresésének egy listában, amit slice segítségével valósítottak meg?

Go-ban a slice egy dinamikus tömb, amely elemeket tárol egymás után a memóriában. Egy elem érték szerinti keresése a slice-ben végig kell nézni az összes elemet, mivel a slice nem indexelhető érték szerint.

Ezért az elem keresésének időbeli komplexitása a slice-ben O(n), ahol n a slice elemeinek száma.

Elem keresésének példája:

func contains(slice []int, val int) bool {
    for _, item := range slice {
        if item == val {
            return true
        }
    }
    return false
}

Itt a legrosszabb esetben minden elemet ellenőrizni kell.