I want to know the speed of preorder traversal of an tree. I do not mean its order of magntude which we know is O(n). I want something like 27n operations where an operation is precisely defined. Thanks


1 Answer 1


It's not answerable in the abstract, without a lot more specifics. It depends on intimate specifics of the computer architecture, what counts as "one" operation, how the tree is represented, and many other details that are usually considered a distraction for purposes of analysis of algorithms. And it wouldn't really be useful in practice anyway; these days, the time it takes for an algorithm to complete depends on a lot more than the number of operations. Not all operations take the same amount of time, and more importantly, the memory hierarchy plays a huge role in influencing the running time, and you can't measure its impact by counting operations.

  • 2
    $\begingroup$ From a book about the ancient 68020 processor: “Calculating exact execution times is very difficult even with complete knowledge of the processor architecture” (quoting Motorola engineers from memory). Today… forget it. Even measuring execution times in a meaningful way is hard. $\endgroup$
    – gnasher729
    Commented Dec 3, 2021 at 8:07
  • 1
    $\begingroup$ Today, one algorithm isn’t on its own. It is often possible to make one algorithm run faster at the expense of other processes running on the same computer. For example, a computer with 12MB cache shared between 4 cores. If your algorithm takes advantage of more memory (12MB instead of its 3MB share) it may run faster but make other processes slower. $\endgroup$
    – gnasher729
    Commented Dec 3, 2021 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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