Exercise $3$:

Compare the efficiency of your algorithm with the brute force using following empirical

approach:

$$ Implement the brute force algorithm to find the minimum distance between any two points

$$ Implement the transform and conquer algorithm to do the same $($Exercise $1$ above$)$

$$ Run above two codes on randomly generated different numbers of input points $($for

example, $10$ points, $20$ points, $100$ points, $1000$ points, $5000$ points$)$ and note down the

execution times. Make sure that in each trial you generate a random input and then run both

codes on that same input.

$$ Plot the times taken by both algorithms as function of the input size, on the same plot.

$$ Explain the plot $($which algorithm is faster and why?$).$

$$ Select N $($number of points$)$

$$ Generate N random numbers $($make sure all numbers are unique, i$.$e$.,$ no two numbers

are same$)$

$$ For brute force, use two loops and calculate distance of each point from every other

point.

$$ For Transform and Conquer, sort the points first and then use one loop to find distance

between consecutive points.

$$ Run both codes and note down the execution time $($Each language has a built$-$in function

for this. For example, tic toc in MATLAB$/$Octave$,$ ctime in C$,...)$

$$ Repeat above five steps for different values of N$,$ and plot the times vs N$.$

Brute force algorithm has O$($n$^2)$ complexity whereas Transform and Conquer has O$($n

log n$)$ for sorting $+$ O$($n$)$ for finding minimum distance, which overall is O$($n log n$).$ So

Transform and Conquer will show lower execution times.