Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

Computer Science Introduction to Algorithms Time Complexity Efficiency of an Algorithm

Calculating the number of tries

How did you calculate the number of tries increasing by 3 when range is multiplied by ten?

2 Answers

Jennifer Nordell
seal-mask
STAFF
.a{fill-rule:evenodd;}techdegree
Jennifer Nordell
Treehouse Teacher

Hi there, Brittney Coble! I'm not sure here if you're referring to the number of tries they showed on a padlock or a binary search so I will take a crack at both. In the case of a padlock that requires two numbers to open the total amount of possibilities is 100. If we then add an extra number, the total number of possibilities is 1000 which doesn't increase the number of possibilities by a factor of 3, but rather 10. But at that point, we have 10 to the power of 3 (or 10 cubed).

Now, if you meant the binary search, in the worst case scenario with 10 elements our search will take us 4 tries. With 100 elements, the worst case scenario will take us 7 tries. Let's start trying to find the number 10 of 1 to 10. Our first guess would be 5, our second guess would be 8, the third guess would be 9, and our 4th guess would be 10. But remember, this is the worst case scenario. In the instance we have 100 elements and we're trying for the last one (100), the first guess would be 50, the second guess 75, the third guess 88, the fourth guess 94, the fifth guess 97, the sixth guess 99, and the seventh guess 100. You can find a breakdown of the number of tries for these in a chart under the "Teacher's Notes". For each factor of 10, the number of tries required in the worst case scenario increases by approximately the square root of 10. You will notice that some increase by 3 where some increase by 4.

Hope this helps! :sparkles:

edited for additional note

Steven Parker is correct about the log base 2 of 10 vs log base 2 of 100. You can find an online calculator here. As he correctly noted, some rounding will need to be done, but the difference between tries is roughly the square root of the factor you're increasing by (at least in a binary search).

Steven Parker
Steven Parker
220,425 Points

A binary search (also known as a "half-interval search") requires a number of tries (in the worst case) of the log base 2 of the range. So for a range of 10, the tries would be 4. Increasing the range by a factor of 10 to 100 would require 7 tries.

So that 3 is the difference between the log base 2 of 10 (rounded up) and the log base 2 of 100 (also rounded up).