The last time I talked about Big-O notation was three days ago, when talking about whether or not inserting/deleting from a list should be done online or queued up:
Zarel: and for insertions, aren't they O(nm) for n insertions into a list of size m either way?
Cathy: inserting n elements into a list of size m when done with queueing requires at most m iterations
Cathy: when not done using a queue, it requires at most n*m iterations
Cathy: a factor of n is the difference
Cathy: of course, n might be pretty small, depending on how many insertions happen in the debounce wnidow
Cathy: n might be 10-15
Zarel: how do you insert n elements into a list of size m in m iterations?
Cathy: iterate over the list of m elements
Cathy: well, i guess you'd need to sort the list of n elements first
Zarel: oh, I see, I forgot about sorting the list
Zarel: so it'd be O(n+m)
Zarel: which is admittedly much faster for our purposes
Zarel: well, considering n is likely to be approximately 5, "much" might be an exaggeration
Cathy: in any case, i agree that inserting/deletion approach is the right way to do this
Zarel: incidentally if we wanted we could apply certain optimizations to improve an insertion from O(n)
Zarel: for instance, binary search
Cathy: it's not immediately obvious whether that is faster than the sorted queued
Zarel: actually, that's not a bad idea regardless
Cathy: but it's certainly faster than the naive single insertion
Zarel: I mean, O(n log m) is significantly faster than O(n+m)
Zarel: when n is ~5 and m is ~1500
Cathy: true, and it actually makes it clear that using a queue is unnecessary
I don't know of a better way to discuss optimizing an inner loop than to use big O notation.
