# Repeated or conditional evaluation to solving which values of n insertion sort beats merge sort

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.

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

$$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.

• 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. – Kevin Liu Feb 27 '18 at 10:34
• @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? – David Richerby Feb 27 '18 at 12:41
• 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. – Kevin Liu Feb 27 '18 at 13:56
• @KevinLiu: I hope we can attribute your arrogance to young age... – Yves Daoust Feb 27 '18 at 13:57
• 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. – Kevin Liu Feb 27 '18 at 18:02