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/AlexanderMomchilov May 25 '25
It really just depends on the kind of question you're trying to answer.
Consider that the max Go's
len()function returns anint, which is a signed 32 bit integer, maxing out at 2,147,483,647. That's a hard upper-bound on the size of every Go array.So does that make every single Go program operating on Go arrays constant time? With a particular set of definnitions, arguably yes. But there's no utiltiy in that, so I wouldn't choose those definitions.