Binary tree execution time calculation - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Binary tree execution time calculation

adaradar Posts: 2Member
I have this question, that's,

Q1) if 1000 elements in a binary search tree takes one second to search an element, how long it will take for 10,000 elements ?

Answer)
Big O for binary search tree O(log N). That means 1000 elements, log 1000 (base 2) = 9.96 ~= 10 comparison takes 1 second
For 10,000 element, log 10000 = 13.28 ~= 13 comparison, 13/10 = 1.3 seconds.
It takes 1.3 seconds for 10,000 elements.

Q2) Similarly one million elements binary tree takes one 1 second to search an element how long it take for 10 million elements?

Answer)
For one million elements, log(1,000,000) = 19.93 ~= 20 comparison in 1 second.
For 10,million elements, log(10,000,000) = 23.25 ~= 23 comparison.
That's 23/20 = 1.15 seconds.

I am not sure whether I did the calculation correct. Please confirm and correct my calculation.


Sign In or Register to comment.