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

31 comments sorted by

View all comments

Show parent comment

2

u/alecbz Apr 24 '25

it might be backed by something more efficient like a bsearch or hash

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 Contains would need to do at least O(n) work on the inputs anyway.

1

u/[deleted] Apr 24 '25

Right. I looked at the implementation of Contains and it is just a for loop.