deletions | additions       diff --git a/subsection_Linear_Separability_We_are__.tex b/subsection_Linear_Separability_We_are__.tex  index be0bba6..7275174 100644  --- a/subsection_Linear_Separability_We_are__.tex  +++ b/subsection_Linear_Separability_We_are__.tex 
...
\mathbf{uq} + v &< 0 \quad \forall q\in\Q \\  \end{align}  This is a system of linear constraints in three-dimensions: we seek values of $u_1, u_2$ and $v$. We only seek a feasible solution, so we set our objective function  to bea  constant.In class we were shown a randomised algorithm which ran in expected $O(d!n)$ time where $d$ was the dimensionality of the data. This was demonstrated in the plane, but we will show how we maintain linearity in three-dimensions.  Our In class we were shown a randomised algorithm which ran in expected $O(n)$ time. This was demonstrated in the plane, but we will show how we maintain running time in three-dimensions.   The  algorithm iteratively adds constraints and maintains an optimal solution on the shrinking feasible region. The running time is dominated by when our current optimal solution is not in the region defined by our new half-space. As argued For the $i-$th added constraint the probability of this occuring is $\leq \frac{3/i}$. This comes by the exact same backward-analysis conducted  in class class. The difference in numerator is a result of the fact that three of our linear constraints determine the optimal vertex in $\mathbb{R}^3$.  So what's our computational complexity when we have to update our optimum? Well as in class, we're only concerned with the intersection of our feasible region and new constraint. In three dimensions this takes the form of a 3D polyhedron and a plane. It's easy to see either geometrically or algebraically that this intersection is in fact a polygon (with $O(i)$ edges). As such, finding  our optimal value on this intersectional plane is a two-dimensional linear problem. This is exactly the class of problems we handled in-lecture, therefore our runtime is expected $O(i)$.  Putting everything together, we have that the expected runtime is:  $$  \sum_i^n \frac{3}{i} O(i) = O(n)  $$