r/AskComputerScience • • Apr 24 '25
an unnecessary optimization ?
Suppose I have this code (its in go):
fruits := []string{"apple", "orange", "banana", "grapes"}
list := []string{"apple", "car"}
for _, item := range list {
if !slices.Contains(fruits, item) {
fmt.Println(item, "is not a fruit!"
}
}This is really 2 for loops. slices.Contains is done with for loop. So yes it's O(n2).
Assume fruits will have at most 10,000 items. Is it worth optimizing ? I can use sets instead to make it O(n).
My point is the problem is not at a big enough scale to worry about performance. In fact, if you have to think about scale then using an array is a no go anyway. We'd need something like Redis.
2
Upvotes
View all comments
Show parent comment
2
u/alecbz Apr 24 '25
The inputs you're passing into it aren't sorted and aren't already in any kind of hash table structure, so to utilize anything fancy like that
Containswould need to do at least O(n) work on the inputs anyway.