By Lemma 2, there are at maximum kN cells that fall in either case 2 or case 3.
by Lemma 1, the amount of work for each of these cells is bounded by ck for some constant c. the theorem is proved.2 If |E| ≤ k for a constant k, the theorem proves the complexity will be O(N ).