Consider the implementations of insertion sort and merge sort,
which has done on the same machine. Here, for inputs of
size
, insertion
sort runs in 
steps,
while merge sort runs in 
steps.
Now, check for which values of , insertion
sort beat merges sort.
(
, since
minimum 2 values are required to sort.)
Consider 
:
Calculate the number of steps required for Insertion sort:
Calculate the number of steps required for Merge sort:
Hence, for insertion
sort beats merge sort.
Consider 
:
Calculate the number of steps required for Insertion sort:
Calculate the number of steps required for Merge sort:
Hence, for insertion
sort beats merge sort.
In the same way, check for every value of n.
When the value of 
, merge sort
beats insertion sort.
Consider :
Calculate the number of steps required for Insertion sort:
Calculate the number of steps required for Merge sort:
Hence, for merge sort
beats insertion sort.
Hence, from the above results, the insertion sort beats merge
sort between the intervals
.
Consider the problem to find the smallest value of 
such that
an algorithm whose running time is 
(say first
algorithm) run faster than an algorithm whose running time is
(say second
algorithm).
Now, calculate the running time of both the algorithms for different values of n.
(
, since
minimum 2 values are required to sort.)
Consider
:
Running time of first algorithm is calculated as follows:
Running time of second algorithm is calculated as follows:
Hence, for second
algorithm take less time as compare to first algorithm.
Consider 
:
Running time of first algorithm is calculated as follows:
Running time of second algorithm is calculated as follows:
Hence, for second
algorithm take less time as compare to first algorithm.
In the same way, check for every value of n. when the value of
become
at
:
Consider :
Running time of first algorithm is calculated as follows:
Running time of second algorithm is calculated as follows:
Hence, for second
algorithm take less time as compare to first algorithm.
Consider 
:
Running time of first algorithm is calculated as follows:
Running time of second algorithm is calculated as follows:
Hence, for first
algorithm take less time as compare to second algorithm.
The first algorithm (whose running time 100 n 2 ) runs faster than the second algorithm (whose running time is 2 n ) when n is 15 or greater .
Therefore, the smallest value of n is 15.