15 Efficiency

\begin{array}{cccc} operation & Sorted List & Tree & Binary Search Tree* \\ search & O (\log n) & O (n) & O (h) : O (\log n) \\ insert & O (n) & O (1) & O (h) : O (\log n) \\ delete & O (n) & O (n) & O (h) : O (\log n) \end{array}

*Binary Search Tree must be balanced
if balance $\log_{2} (n) \leq h \leq n$
Otherwise a BST is $O (n)$

![](/img/user/Introduction to CS/attachments/Pasted image 20250410153613.webp)

$O (1) \subseteq O (l g (n)) \subseteq O (n) \subseteq O (n^{2}) \subseteq O (n^{3}) \subseteq O (2^{n}) \subseteq O (n!) \subseteq O (n^{n})$

$θ (g (c))$ if there exists $c_{1}, c_{2}$ s.t $c_{2} g (n) < f (n) < c_{1} g (n)$ ignoring any coefficients.