[robconery]

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]

> 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]

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.