# Misc Randomized Algs

Tags AlgorithmsCS161

# 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 $m$﻿, and in order of $b$﻿ as a tiebreaker. Comparisons are done ad-hoc). This is $O(n^2 \log n^2)$﻿.
1. 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$﻿.
1. For all other points, see if they lie on this line formed by the pair. This takes $O(n)$﻿ time
1. 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)$﻿.