Michael Lefkowitz

Time Complexity and Logarithmic Bar Tricks

September 11, 2016

In the past couple of days, we have dived deep into data structures and time complexity. Learning the intricacies of computer science has been a rewarding challenge - and has resulted in quite a few “aha” moments. My personal favorite thus far has been binary search trees - especially realizing just how quickly a computer can find a value using an algorithm based on logarithmic complexity. But, even more interesting was realizing that a human can pull that off too. Let’s call it a logarithmic bar trick.

  1. Tell someone you can guess a number between 1 and 1,000,000 in twenty or less guesses, provided they let you know whether your guess is high or low
  2. Use an algorithm of logarithmic complexity O(log n) to guess
  3. ?????
  4. Profit

How does that work exactly? Every time you guess, you’re breaking down the original sample size by 50%. So your first guess is going to be 500,000. They tell you it’s higher. Your second guess is 750,000. They tell you it’s higher. At this point you’ve only made two guesses and you’ve already eliminated 75% of the possibilities. Keep up with this method, and you’ll have their number in twenty guesses tops.

Let’s see how that would look in Javascript.

var min = 1;
var max = 1000000;
var guess;
var number = Math.floor(Math.random() * max) + min;
var counter = 0;

while (guess !== number){
        counter += 1;
	guess = Math.floor((min + max) / 2);
	console.log('Guess #' + counter + ':', guess);
	if (number > guess){
		min = guess + 1;
		console.log('Number is higher');
	} else if (number < guess) {
		max = guess - 1;
		console.log('Number is lower');


First, we set our min and max variables. Then, we’ll create a variable to hold our guesses called guess. Next, we’ll set a number variable to a random integer between our min and max. And lastly, I want to keep track of how many guesses it’s going to take to find the number, so let’s create a counter variable and set it to 0.

Then, we build a while loop which will continue to run until our guess variable is equal to our number variable.

Inside of our loop, we first increment our counter variable. Next, we set the guess variable equal to to the average of the min and the max combined.

Next, we setup an if statement that’s going to check whether our guess variable is higher or lower than the number. If our guess is too high, we’re going to set our max variable to one less than the current guess. If it’s too low, we’ll set the mix variable to one more than the current guess. That’s all there is to it.

For fun, I went ahead and wrapped this in a function, dropped the function call in a for loop that ran 10,000 times, and pushed the counter results to an object after each run. When only running it once, I rarely would see the algorithm find the number in less than 16 guesses. But, when running it 10,000 times, I was able to catch the program guessing correctly on the first try at least once.

Want to up the ante? Tell your friend you can guess a number between 1 and 1,000,000,000 in thirty or less guesses. Thirty? Yup. Just take your maximum number and continually divide by 2 until you hit one or less. The amount of times it takes you to get there is equal to the maximum amount of guesses needed.

1,000,000,000 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 = 0.93

Helpful links: