Misc Randomized Algs


Colinear points

This one has both a non-random and a random solution

Nonrandom solution

  1. Get all pairwise points
  1. Sort these pairwise points lexographically (in order of mm, and in order of bb as a tiebreaker. Comparisons are done ad-hoc). This is O(n2logn2)O(n^2 \log n^2).
  1. Find the longest run. This is O(n2)O(n^2), but it is overshadowed by the sorting so the final complexity is O(n2logn2)O(n^2 \log n^2)

Random solution

If we knew that the length of the longest run is n/kn/k, then this is what we do:

  1. pick a random pair of points, compute m,bm, b.
  1. For all other points, see if they lie on this line formed by the pair. This takes O(n)O(n) time
  1. If the ending count is n/kn/k, then return the set. Otherwise, pick another random pair of points.

The worst case runtime is O()O(\infty), but what about expected runtime? Well, how likely are we to pick the right set of points? There are n/kn/k points in the longest line, so the chance of us picking a pair of points is

n/knn/k1n1\frac{n/k}{n}\frac{n/k - 1}{n-1}

We can simplify into

1k2nkn11k2\frac{1}{k^2}\frac{n-k}{n-1} \leq \frac{1}{k^2}

Therefore, the probability of getting a pair within the longest run is within O(1/k2)O(1/k^2). Now, if we treat it as a goemtric random variable, it means it will take around k2k^2 tries to get this pair. As such, our final expected compelxity is k2O(n)k^2 O(n), or O(k2n)O(k^2n).