err, i'm not sure i agree with you on that point, solar, having T(10)=0.5*T(100)=0.25*T(1000) isn't a logarithmic complexity. Logarithmic complexity says T(100)=T(10)+k and T(1000)=T(10)+2*k, T(10000)=T(10)+3*k, etc.Solar wrote:
If execution time roughly doubles for every order of magnitude of n (like, 100 tasks take twice as long as 10 tasks), that's O(log(n)) - "logarhitmic complexity", and you have one of the best algorhithms around.
However, it's unfrequent to have base-10 logarithmic complexity. Base 2 is more common (for binary trees, for instance): everytime your dataset is doubled, your processing time increases by a constant value K.
