1
$\begingroup$

Suppose a comparison between elements takes 1ms to execute. If an algorithm is O(logN), for example, deletion in an AVL Tree, and the AVL Tree contains 100 elements. Does that mean that the time to execute the algorithm would be log100 * 1ms? Do I need more information to calculate this or is this enough?

$\endgroup$
1
$\begingroup$

If an algorithm is $O(\log n)$, then you can conclude absolutely nothing about the running time of the algorithm. This is due to many factors, one of which is that $O(\log n)$ hides an arbitrary constant factor: both $\log n$ and $100\log n$ are $O(\log n)$ (not to mention functions such as $10^6\log\log n + 10^{15}$). There are also other reasons, but this reason is probably enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.