Question

What is the smallest value of n such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine?

Comments

100n² < 2ⁿ

For n= 15, 100n² run faster than 2ⁿ  i.e. 22500 < 32768

Answer 1

At $n=14$, $2^n-100n^2 = 2^{14}-100*14^2 = -3216$

At $n=15$, $2^n-100n^2 = 2^{15}-100*15^2 = 10268$

So at $n=15$, $2^n$ becomes greater than $100n^2$

Comments

But this becomes a preety easier when we use C/C++.

are we allowed to do so in GATE :P ?

---

No, just use calculator and a bit of binary search manually, I found it through that only.