1
$\begingroup$

If one algorithm has a running time of $100n^2$ and another of $2^n$; how can I find the smallest value of $n$ such that the former is faster than the latter?

I could do: $100n^2 < 2^n$ then $\ln(100n^2) < n\ln(2)$ but how do I simplify the left side?

$\endgroup$
2
  • 2
    $\begingroup$ You try a few values of $n$, get some feeling for what's going on, try a few more values of $n$, and zero in on the answer. $\endgroup$ Jul 5, 2013 at 12:44
  • 1
    $\begingroup$ An explicit form for the intersections of the two graphs is difficult to obtain. An iterative/heuristic approach probably your best shot: W|A link $\endgroup$
    – apnorton
    Jul 6, 2013 at 3:23

1 Answer 1

2
$\begingroup$

The best method could be to plot a rough graph of 100*n^2 and 2^n on the same pair of axes. Then see a probable point of intersection by some iterative method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.