The Cover Tree algorithm was created by Beygelzimer et
al.\cite{CoverTrees} in 2006. It forms a tree with the top level of
the tree being of level $i$, where $i \geq $the number of levels in
the tree. Starting at the root node, as the tree is descended, $i$
decrements. At each node of the tree, the distance between any two
points of the node's children is greater than $2^{i-1}$. At least one
point $p$ in the node is within $2^i$ of any point $q$ in the node's
children.

Cover trees have a maximum insertion time of $O(c^6n ln(n))$\cite{CoverTrees}, where c is the dimensionality of the
dataset. This insertion time is theoretical and represents the worst
case scenario. While the creation time is high, the querying time is
only $O(c^{12} ln(n))$. 
%\input{figures/pseudo-code/cover}
