Colinear points

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

Nonrandom solution

1. Get all pairwise points

2. Sort these pairwise points lexographically (in order of $m$, and in order of $b$ as a tiebreaker. Comparisons are done ad-hoc). This is $O(n^2 \log n^2)$.

3. Find the longest run. This is $O(n^2)$, but it is overshadowed by the sorting so the final complexity is $O(n^2 \log n^2)$

Random solution

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

1. pick a random pair of points, compute $m, b$.

2. For all other points, see if they lie on this line formed by the pair. This takes $O(n)$ time

3. If the ending count is $n/k$, then return the set. Otherwise, pick another random pair of points.

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

We can simplify into

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