Welcome to the Treehouse Community
Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.
Looking to learn something new?
Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.
Start your free trial
Brittney Coble
16,474 PointsCalculating 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
Treehouse TeacherHi 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!
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
231,275 PointsA 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).