# 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.

- 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
- Use an algorithm of logarithmic complexity
`O(log n)`

to guess - ?????
- 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');
}
}
console.log('Number:',number);</pre>
```

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: