Answers To Introduction To Algorithms 1.2-2 and 1.2-3

Algorithm is a fun subject and we are starting from the very basics of algorithm. Here is my solution for selected questions from chapter 1 of Introduction To Algorithms by Cormen and others.

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 8n² steps, while merge sort runs in 64nlg n steps. For which values of n does insertion sort beat merge sort?

Here, we need to determine the value of n such that 8n² = 64nlgn

For the value n = 1, obviously the merge sort beats the insertion sort so we will start from 2 and find the higher limit up to which the insertion sort beats merge sort.

The above equation can be further reduced as n = 8lgn. We can now solve it to determine the value of n. A simple code in C that would do the job for us is as below:

#include <stdio.h>
#include <math.h>

int main()
{
 int i = 2;
 while (1)
 {
  int merge = 8 * log2(i);
  if (i > merge)
  {
   printf("Value of i: %d\n", i);
   break;
  }
  i++;
 }
 return 0;
}

Answer: 2 <= n < 44. 1.2-3) What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2n on the same machine?

Here, we need to determine the smallest value of n such that 100n2 < 2n. The value of n evaluates to 15. The source code for above problem is as below:

#include <stdio.h>
#include <math.h>

int main()
{
 int i = 2;
 while (1)
 {
  int x = 100 * pow(i, 2);
  int y = pow(2,i);
  if (x < y)
  {
   printf("Value of i: %d\n", i);
   break;
  }
  i++;
 }
 return 0;
}

I hope this helps some of the algo beginners out there trying to solve the questions from "Introduction To Algorithms". Btw, they are basic maths however :P