[Introduction to Algorithms, CLRS] Exercise 1.2-2

This is a solution for Introduction to Algorithms. I write this for my study purpose.

1.2-2

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort? 

Answer:

So the question is when the following will be...:

8n2   < 64n lg n

We can solve this equation as follows:

It is obvious that insertion sort runs at quadratic time which is definitely worse than merge sort’s linearithmic time for very large values of n. We know for n=1, merge sort beats insertion sort. But for values greater than that, insertion sort beats merge sort. So, we will start checking from n=2 and go up to see for what value of n merge sort again starts to beat insertion sort.

Notice that for n<8, 2n/8 will be a fraction. So, let’s start with n=8 and check for values of n$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}$ which are power of 2.

n=8⟹28/8=21=2<8$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">1</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;"><</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}$ n=16⟹216/8=22=4<16$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">16</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">16</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">4</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;"><</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">16</span>}$ n=32⟹232/8=24=16<32$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">32</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">32</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">4</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">16</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;"><</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">32</span>}$ n=64⟹264/8=28=256>64$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">64</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">64</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">256</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">></span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">64</span>}$

$\mathrm{<br>}$

Somewhere between 32 and 64, merge sort starts to beat insertion sort. Let’s do what we were doing but now we are going to try middle value of either range, repeatedly (binary search). 

n=32+642=48⟹248/8=64>48$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\frac{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">32</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">+</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">64</span>}}{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">48</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">48</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">64</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">></span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">48</span>}$ n=32+482=40⟹240/8=32<40$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\frac{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">32</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">+</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">48</span>}}{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">40</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">40</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">32</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;"><</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">40</span>}$ n=40+482=44⟹244/8=44.8>44$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\frac{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">40</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">+</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">48</span>}}{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">44</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">44</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">44.8</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">></span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">44</span>}$ n=40+442=42⟹242/8=38.4<42$\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">n</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\frac{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">40</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">+</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">44</span>}}{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">42</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">⟹</span>{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">2</span>}}^{\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">42</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">/</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">8</span>}}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">=</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">38.4</span>}<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;"><</span>\mathrm{<span\; style="font-family:\; "맑은\; 고딕",\; sans-serif;\; font-size:\; 11pt;">42</span>}$ n=42+442=43⟹243/8=42.4<43

So, at n=44, merge sort starts to beat insertion sort again. Therefore, for 1<n<44, insertion sort beats merge sort.

source: http://atekihcan.github.io/CLRS/E01.02-02/