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 have a non-linear equation. These can often be transformed to the form x = f(x), then choosing a start value x and repeatedly calculating f(x) will converge to a solution, if the function f is chosen well.

In this case 100n^2 = 2^n or log (100n^2) = n log 2 or n = log(100 n^2) / log 2. Start for example with n=1 then replace n with log (100n^2) / log 2 repeatedly. You will get results n=7, n= 12, n= 14, n = 15.

Answer 2

You want to find the value of $n$ for which $100n^2 \approx 2^n$. Taking logs, we get $2\log n + 7 \approx n$, so $n \approx 7 + 2\log 7 \approx 13$. Of course, this is just an approximation.

Answer 3

Having a computer check those large results by brute force could cause integer overflow pretty quickly.

My approach scales down the results, but you’ll still need to solve an equation. Assuming n > 0, we want to solve the inequality

$$2^{n} > 100n^{2} $$ Taking the log of both sides yields $$n > log(100) + log(n^2)$$ $$ n > 6.64 + 2log(n)$$ $$ n > 7 + 2log(n)$$ $$ n - 7 - 2log(n) > 0$$

We could then solve with a loop to get our value of n.

pseudocode 
 n = 1
while (n - 7 - 2log(n) <= 0 )
    n = n + 1

When the loop exits in approximately 14 iterations, we should have the value of n.