Algorithms For Dummies

  Using Randomized Algorithms 

     335

If on average it takes about three times the size of the input, Quickselect is provid-

ing good performance. However, you may wonder whether the proportion between 

inputs  and  computations  will  hold  when  the  input  size  grows.  As  seen  when 

studying  NP-complete  problems,  many  problems  explode  when  the  input  size 

grows. You can prove this theory by using another Monte Carlo simulation on top 

of the previous one and plotting the output, as shown in Figure 17-5.

input_size = [501, 1001, 5001, 10001, 20001, 50001]

computations = list()

for n in input_size:

    results = list()

    for run in range(1000):

        series = [randint(1, 25) for i in range(n)]

        median,count = quickselect(series, n//2)

        assert(median==np.median(series))

        results.append(count)

    computations.append(np.mean(results))

plt.plot(input_size, computations, '-o')

plt.xlabel("Input size")

plt.ylabel("Number of computations")

plt.show()

Completing the computations from this example may take up to ten minutes (some 

Monte Carlo simulations may be quite time consuming), but the result helps you 

visualize what it means to work with an algorithm that works with  linear time. 

As the input grows (represented in abscissa), the computations ( represented on 

the ordinal axis) grow proportionally, making the growth curve a perfect line.

FIGURE 17-4: 

Displaying the 

results of a 

Monte Carlo 

simulation on 

Quickselect.

---

336

 

   

  PART 5