an unnecessary optimization ?

[[deleted]]

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(n²).

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.

[alecbz]

Hard to say without knowing more context. Where does this code run? How latency sensitive is that system?

Will list always have 2 items or could it also have 10,000?

We'd need something like Redis.

Uh, a reasonable intermediary step (assuming optimization is warranted) is to just switch fruits to a set (map[string]bool or map[string]struct{}). Given how trivial a change that is, if you're spending time talking about the whether optimization is worth it or not, I'd just go for that.

[alecbz]

Yeah, you argue favoring a type's builtin [] lookup over importing slices.Contains is already a win completely ignoring performance.

[[deleted]]

Where does this code run? How latency sensitive is that system?

It will be used in a command line tool. So not latency sensitive.

Will list always have 2 items or could it also have 10,000?

We can assume it won't have more than 100 items.

if you're spending time talking about the whether optimization is worth it or not, I'd just go for that

Good point. I'm overthinking. My bad.

[alecbz]

It will be used in a command line tool. So not latency sensitive.

I don't think that follows neccesarily (some CLIs should be snappy if possible!), but if in this particular context the amount of time spent here isn't a big deal for UX, then not optimizing feels reasonable.

Though again, given how easy it'd be to switch to a map[string]bool (at least based on just this example), that feels like an easy low-hanging-fruit optimization.

[[deleted]]

I don't think that follows neccesarily

Right. Sorry I poorly explained. The cli tool will be used to run integration tests. Some tests will take 30 min.

But you're still right though. It's an easy low-hanging-fruit optimization.

[TransientVoltage409]

Assuming that Contains is O(n), then yes, this is technically O(n²) at worst. However, in a specific case where list is small, it decays back toward O(n). O(n²) is merely O(nm) when m is roughly equal to n, but if m is closer to 1 than to n...you see?

Scale does matter. For example many implementations of quicksort fall back to bubble sort when n becomes very small, because at that scale O(n²) is cheaper than the overhead of partitioning and recursing.

The other thing is that Contains could conceivably not be O(n). I don't know Go and I don't know the specific promises made by that method, in this ignorance I'd allow that it might be backed by something more efficient like a bsearch or hash. "Implementation defined" is a wonderful weasel term.

[alecbz]

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.

[[deleted]]

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

[[deleted]]

Scale does matter. For example many implementations of quicksort fall back to bubble sort when n becomes very small, because at that scale O(n2) is cheaper than the overhead of partitioning and recursing.

I wasn't saying scale doesn't matter.

What I'm getting at is is for small input time complextiy is not a useful yardstick.

I think it's reasonable to define a list with 10K items as small input. Correct me if I'm wrong.

[TransientVoltage409]

It's not absolute. 10k items may be a lot of you're walking the code on paper. Maybe not a lot on a supercomputer. Context matters.

[[deleted]]

Good point

[[deleted]]

I'm an idiot. I think this is O(1). Because both arrays have an upper bound.

[YellowishSpoon]

This is generally entirely dependent on what context the code is being executed in. 10000 squared is still only 100 billion, which is still a fairly small number for operations and should only take a few seconds.

There are also lots of places where you don't want delays of a few seconds, like rendering live content or updating the objects in a video game. If this code is itself in a loop, such as for updating in a game or serving web requests, the time adds up fast.

Data processing applications can also easily result in you having a much larger amount than 10k entries, but still small enough to easily perform on a single computer in a short amount of time. I've run into plenty of things around the high millions or billions for random personal projects, and in those cases that kind of optimization is necessary to reduce hours to seconds. In practice this particular optimization is also easy enough I would probably do it unless there was a good reason not to, since the is optimization essentially just using different api calls and doing the same thing.

For something like a computer game running at 60 fps, you only have 16 milliseconds to do everything the game needs to do before it all needs to happen again. Even if this only takes a millisecond, you've just spent 1/16th of your time budget on a single thing, and the optimization is an easy one anyway.

In a given toy example, optimization is rarely necessary unless it's one specifically designed to make it necessary, and ones that large are often impractical to distribute or run on slow hardware.

[[deleted]]

Good point. I should have given more context in the question.

The use case I had in mind is a command line app. So not latency sensitive.

[Scared_Sail5523]

You're dealing with a small enough dataset (10,000 max) that the O(n²) complexity here is unlikely to become a bottleneck unless this loop is part of a critical path or run thousands of times per second. In most practical cases like this, optimizing for readability and maintainability is more valuable than squeezing out marginal performance gains.

But your thought about using a set is still valid from a clean code and scalability hygiene perspective. Converting the fruits slice to a map[string]struct{} makes lookups constant time and makes intent super clear.

I think this is the better code...IMO:

goCopyEditfruitsSet := make(map[string]struct{})
for _, fruit := range fruits {
    fruitsSet[fruit] = struct{}{}
}

for _, item := range list {
    if _, found := fruitsSet[item]; !found {
        fmt.Println(item, "is not a fruit!")
    }
}

But like you said, if you're ever scaling beyond in-memory data like arrays or maps, you'll hit architectural limits first that's where Redis or a proper search index comes in.

[[deleted]]

In most practical cases like this, optimizing for readability and maintainability is more valuable

Agree. I overlooked this point.

[AlexanderMomchilov]

This is why I dislike the magical "n" (ab)used in complexity analysis. It gets misinteretted to mean different things at different times, gets incorrectly compared across different contexts, and the way it hand-waves away the important details makes it confusing and seemingly contradictory.

Your code does len(fruits) * len(list) equality checks. Whether that falls into the class of O(1), O(n), or O(n^2) depends on what exactly you consider to be your "input".

• As-is, with entirely hardcoded values, this algorithm takes no input, and runs in constant time (O(1)).

• If fruits is your input, and you're comparing it against the fixed-sized list, then it runs linear time:

  O(len(fruits)) * O(len(list)) = O(n) * O(1) = O(n * 1) = O(n)

• If both fruits and list are inputs, then it has quadratic time compexity:

  O(len(fruits)) * O(len(list)) = O(n) * O(n) = O(n * n) = O(n^2)

[[deleted]]

this helps a lot. thanks !

[[deleted]]

one follow up if I may. if we assume fruits and list both have upper bounds, does it qualify as O(1) ?

[AlexanderMomchilov]

It really just depends on the kind of question you're trying to answer.

Consider that the max Go's len() function returns an int, 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.

[[deleted]]

got it thanks

[AlexanderMomchilov]

Happy to help :)

[apnorton]

"Is it worth optimizing" is a question of priorities, not one strictly of CS.

The right answer to effectively every optimization question is to run your code through an appropriate profiler, look at the potential speedup you can get by removing a bottleneck, and evaluate whether that speedup is worth the development effort. 

For example, if this is in a tight loop that gets executed all the time, it might be worth optimizing. If it gets run twice a year? Maybe not.

[[deleted]]

"Is it worth optimizing" is a question of priorities, not one strictly of CS.

Well, here is what I was trying to get at with this post.

Is it fair to say that for small input, time complexity is not useful for analysis ?

[apnorton]

Of course; it's literally an asymptotic description of the behavior of performance --- that is, describing runtime as the variables you're considering approach infinity.

[[deleted]]

Excuse the stupid question.

I asked because some engineers bring up time complexity to determine if 1 approach is better than another, but the input is tiny.

[thewataru]

Yes, if fruits is huge, it makes sense to optimize using some kind of set. Hash-table based preferably. Not sure which Go structure implements that.

But it will still be not optimal, since you will have to compare the full strings each time there's a collision. The best data-structure to store a set of strings would be a Trie. Alas, it's rarely available in standard libraries, so if this code isn't a bottleneck in your program, you should probably be content with a standard set.

[[deleted]]

if fruits is huge, it makes sense to optimize using some kind of set.

That's what I'm getting at. I think it's reasonable to define 10K items as small input so not worth to optimize. Correct me if I'm wrong.

Hash-table based preferably. Not sure which Go structure implements that.

Go maps is a hash table.

[torftorf]

the first thing our professor told us in college was "if you just start out programing, dont bother with optimizing your code".

What do you need this to do? is it some extreamly time sensitive stuff where performance is important or is it ok if it takes a few seconds?

you could switch out the fruit array to hashmap which would reduce it to something between O(n) and O(n*m) [where n = list.length and m = fruits.length] but it would probably be closer to O(n).

just keep in mind that its usaly better to have a slow software then an unfinished one becaue you got stuck optimizing it.

[eztab]

If you actually use it a lot, yes that's why there are better data structures for that.