-4
$\begingroup$

I'd like to solve the questions below with repeated or conditional evaluation but I don't know how.

  1. Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n*log(2,n)$ steps. For which values of $n$ does insertion sort beat merge sort?

  2. 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?

Any pseudocode would help me so much. Thank you.

$\endgroup$
  • 2
    $\begingroup$ This seems to be a basic math question, disguised as time complexity analysis, or perhaps an elementary programming question. $\endgroup$ – Yuval Filmus Feb 27 '18 at 9:16
  • $\begingroup$ Is the analytical solution really that simple? math.stackexchange.com/questions/2666503/… $\endgroup$ – Kevin Liu Mar 1 '18 at 0:57
1
$\begingroup$

$$8n^2<64n\lg n\iff \frac n{\lg n}<64.$$

Using a grapher, $n\le588$.


$$100n^2<2n\iff n<\frac1{50}$$

There is no solution.

$\endgroup$
  • $\begingroup$ I already knew the answer, I am looking now for the mathematical process to reach the answer. The computational one I just fully described below. $\endgroup$ – Kevin Liu Feb 27 '18 at 10:34
  • 2
    $\begingroup$ @KevinLiu Honestly, this is ridiculous. You come here asking us to do your homework for you, somebody (IMO misguidedly) does so and you respond with a bunch of demands. Who on earth do you think you are? $\endgroup$ – David Richerby Feb 27 '18 at 12:41
  • 1
    $\begingroup$ Daoust's answer is incorrect, as it applies to $2n$, and not $2^n$. As to my ancestry, feel free to visit en.wikipedia.org/wiki/Liu, but I believe that is off-topic. $\endgroup$ – Kevin Liu Feb 27 '18 at 13:56
  • 1
    $\begingroup$ @KevinLiu: I hope we can attribute your arrogance to young age... $\endgroup$ – Yves Daoust Feb 27 '18 at 13:57
  • 1
    $\begingroup$ It appears the analytical solution to this problem is the Lambert W function, as mentioned by Joffan math.stackexchange.com/questions/2666503/…. That is what I meant by mathematical, again my mistake. The solution I posted here is the numerical one. $\endgroup$ – Kevin Liu Feb 27 '18 at 18:02

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.