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!


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 ?

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?

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.