Suppose that for inputs of size n on a particular computer, insertion sort runs in steps and merge sort runs in steps. For which values of n does insertion sort beat merge sort?
💡
We could interpret the question as at what value will the runtime of merge sort start becoming lower than insertion sort
where
This can not be solved algebraically. Possible methods are:
Trial and error, taking a guess and solving till a final solution is reached.
but too difference is too large
We could play with , reducing by a margin of till we get to an approximate value
when
margin still high
when
margin a bit close
when
,
So, is best suited at ; playing with n still but increasing from 40 by 2
when
when
So, when n is approximately , merge sort starts becoming faster than insertion sort
We could reduce further starting from , using a margin of
;
to get a closer range that tells exactly when the value of n starts becoming significant.
when
but the difference is close
From here on ward the fraction gets uglier.
We could settle for
Using Newton Raphson iteration method
Solving numerically:
Newton Method =
We would solve this with a python code instead of solving it here manually.
We take to be 8, and a tolerance of
import math
# Define the function and its derivative
def f(n):
return 2**(n/8) - n
def df(n):
return (1/8) * math.log(2) * 2**(n/8)
# Initial guess
n_guess = 8
# Tolerance for convergence
tolerance = 1e-6
# Maximum number of iterations
max_iter = 1000
# Iterative approximation
for i in range(max_iter):
fn = f(n_guess)
if abs(fn) < tolerance:
print("Solution found: n =", n_guess)
break
else:
# Newton's method: x_{n+1} = x_n - f(x_n) / f'(x_n)
n_guess = n_guess - fn / df(n_guess)
else:
print("Maximum iterations reached. No solution found.")
The result is:
Solution found: n = 43.559260335587204
PS: We did a good job with the manual approach, we just did not get to a precise solution.
Using graphs
We could plot two lines on same graph
a:
b:
And use the intersection point to determine the solution.
