What is the smallest value of n such that an algorithm running at 100*n^2 operates faster than 2^n ? [How to figure out without brute force]

Question

Okay, so I needed to find the smallest value of n such that algorithm 100*n^2 is faster than 2^n.

[what I have tried]

So, I instantly thought '0'. But, I then realized it can't be 0, 0 implies that there are no digits being entered in the algorithm, it also implies that the program does not run or terminate.

I typed in 2^32 and got a number over 4 billion. Okay, this is good, I'm finding numbers that have 100*n^2 being faster than 2^n.

I halved that, n = 20.

I kept inserting values counting down until I got to n = 15.

I also counted up from n = 10, the answer is undoubtedly n = 15, but I have a problem . . . .I solved this using brute force and that isn't good. What if I was given a bigger number and a larger bredth of numbers?

[What I need]

I need a way of finding the value instantaneously by only doing the math, I tried using logarithms, but my answer was wrong, my knowledge of logs is a bit rusty and I need a little help.

Think of it as a student trying to solve a question on an SAT or having a timer for a test.

Answer 1

You might want to look up Binary Search if you are looking for a computer science solution which in this case is much simpler. The alternative is the mathematical solution which is achieved via the Lambert function.

Binary Search

1. Set a lowerbound, $b_l = 1$, and upper bound, $b_u = 32$
2. Set a winning condition, $100n^2 = 2^n$ in this case
3. Pick a value, $n$, that is halfway between those bounds, $n = \frac{|b_l + b_u|}{2}$
4. If $n$ satisfies your winning condition you're done
5. Else if $100n^2 < 2^n$ then set $b_l$ to $n$ and goto step 3
6. Else if $100n^ > 2^n$ then set $b_u$ to $n$ and goto step 3

Kepp repeating these steps until $b_l <= b_u$ and when you terminate the value you have of $n$ is you're required value

Answer 2

In theory you could have an algorithm that terminates in zero steps if no digits are entered. (It depends on exactly how you define things.) But let’s just say you want the smallest positive integer $n$.

Assuming you are not allowed to use a calculator with the Lambert W function (or anything equivalent) built in, I think trial and error is your best bet. On the SAT at least you would only have a small set of choices of $n$ to consider.

You could save some calculations by using the fact that for $n>0,$ $100n^2<2^n$ if and only if $10n<2^{(n/2)}.$ This saves you computing squares and lets you use smaller powers of two. It gets a bit complicated when $n$ is odd, however.

For example, if $n=20$ you have $10n=200<1024=2^{10}.$ So try something smaller, say $n=16.$ Then $10n=160<256=2^8.$ Even smaller, if $n=14$ then $10n=140>128=2^7.$ Next you just need to test $n=15$ to decide whether the answer is $15$ or $16.$