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]

exponentiationlogarithms

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.

Best Answer

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.

Related Question