4 ms·

> I don’t want to turn this into a Redis commercial, but I will say that it (and systems like it) have a lot to offer when you start thinking about things in te

by mbell 8y ago

> I don’t want to turn this into a Redis commercial, but I will say that it (and systems like it) have a lot to offer when you start thinking about things in terms of time complexity, which you should! It’s not premature optimization to think about Big O upfront, it’s programming and I don’t mean to sound snotty about that! If you can clip an O(n) operation down to O(log n) then you should, don’t you think? The thing is, I don't care about 'time complexity', I care about performance. Big O can serve as a useful datapoint for what the performance may be, but it's only that, one data point. e.g. It's not uncommon to find that a 'worse' algorithm/data structure in Big O terms will out perform a 'better' one because the 'worse' one has better cache locality. So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster.

robconery 8y ago
OP here - Big O notation is simply shorthand math. When you're discussing things in this way, time complexity and performance are the same thing. When you care about resource usage (memory etc) that's space complexity, which is different. Either way, they're good things to understand. >So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster. Mathematically the log n is always faster :). Realistically... well that would be a tough one to prove, even with caching, but I say go for it.
- mbell 8y ago
  > time complexity and performance are the same thing By definition, they are not. > Mathematically the log n is always faster :) No, it's not. Time complexity only gives you an asymptotic bound on the number of 'operations', it tells you nothing about what the actual run time will be.
  - robconery 8y ago
    I believe we're talking past each other. Big O has nothing to do with "actual run time*. It doesn't care what about the number of inputs you have - just that you have them. Mathematically, if n=1000 then log n is 10. 10 operations vs. 1000 is, theoretically and time complexity wise, faster. Our disconnect is "actual" vs. "theoretical" and I want to stress again that Big O is purely theoretical. It's a technical adjective.

by mbell 8y ago

robconery 8y ago

OP here - Big O notation is simply shorthand math. When you're discussing things in this way, time complexity and performance are the same thing. When you care about resource usage (memory etc) that's space complexity, which is different. Either way, they're good things to understand. >So no I don't think you should use an O(log n) operation in place of an O(n) operation just because of Big O, what matters is which one is faster. Mathematically the log n is always faster :). Realistically... well that would be a tough one to prove, even with caching, but I say go for it.

mbell 8y ago
> time complexity and performance are the same thing By definition, they are not. > Mathematically the log n is always faster :) No, it's not. Time complexity only gives you an asymptotic bound on the number of 'operations', it tells you nothing about what the actual run time will be.
- robconery 8y ago
  I believe we're talking past each other. Big O has nothing to do with "actual run time*. It doesn't care what about the number of inputs you have - just that you have them. Mathematically, if n=1000 then log n is 10. 10 operations vs. 1000 is, theoretically and time complexity wise, faster. Our disconnect is "actual" vs. "theoretical" and I want to stress again that Big O is purely theoretical. It's a technical adjective.