COMP2402: Asymptotic Runtime Chart in LaTeX

 •  •  ☕️ Reading Time

Here is the final product

Context

At my university COMP2402 is a course about data structures and algorithms. The class revolved around Pat Morin’s book Open Data Structures; it is an excellent read. While the book has good summaries at the end of each chapter, many of my classmates thought it would be good to have a single sheet containing all of the big-O and big-Omega runtimes for the various operations we can apply to data structures.

Creation

I chose LaTeX as it’s my preferred way to typeset documents. Also, being able to use macros (through newcommand) will save me a lot of typing when it comes to the repetitive stuff.

%% Big O runtime macros
\newcommand{\Onminusi}{$\mathcal{O}\left( 1+n-i \right)$}
\newcommand{\Oconst}{$\mathcal{O}\left( 1 \right)$}
\newcommand{\Oonepmin}{$\mathcal{O}\left( 1 + \min{i,n-i} \right)$}
\newcommand{\Oonepi}{$\mathcal{O}\left( 1+i \right)$}
\newcommand{\Ologn}{$\mathcal{O}\left( \log\left( n \right) \right)$}
\newcommand{\Onlogn}{$\mathcal{O}\left( n \log\left( n \right) \right)$}
\newcommand{\Oquad}{$\mathcal{O}\left( n^2 \right) $}

% Omega
\newcommand{\Omeganlogn}{$\Omega\left( n \log\left( n \right) \right)$}
\newcommand{\Omegalogn}{$\Omega\left( \log\left( n \right) \right)$}
\newcommand{\Omegan}{$\Omega\left( n \right) $}

% Theta
\newcommand{\Thetanlogn}{$\Theta \left( n \log (n) \right)$}
\newcommand{\Thetann}{$\Theta \left( n^2 \right)$}

This is going to greatly simplify making tables, as I won’t have to re-type every single symbol declaration for each row and column of the table. Also, if I decide to change the theme or the style of these symbols, I only have to change them in one location.

For creating the tables themselves I used tabularx as it provides dynamically sized columns. Because I want this to look fairly neat, I wrapped each table in a minipage. This way I can easily move them around and make the layout nice and symmetrical.

That’s pretty much it - a quick and simple project. I put the source below if anybody would be interested in building off of it / hacking on it :)

\documentclass{article}
\usepackage[paperheight=6in, paperwidth=8.5in, margin=0.125in]{geometry}
\usepackage[usenames,dvipsnames,table]{xcolor}
\usepackage{tcolorbox}
\usepackage{multirow}
\usepackage{tabularx}
\usepackage{array}
\usepackage{colortbl}
\usepackage{listings}
\tcbuselibrary{skins}

\newcolumntype{Y}{>{\raggedleft\arraybackslash}X}

\tcbset{theme/.style={enhanced,%
    fonttitle=\bfseries,%
    fontupper=\normalsize\sffamily,%
    colback=yellow!10!white,%
    colframe=red!50!black,%
    colbacktitle=Salmon!40!white,%
    coltitle=black,center title}}

%% Big O runtime macros
\newcommand{\Onminusi}{$\mathcal{O}\left( 1+n-i \right)$}
\newcommand{\Oconst}{$\mathcal{O}\left( 1 \right)$}
\newcommand{\Oonepmin}{$\mathcal{O}\left( 1 + \min{i,n-i} \right)$}
\newcommand{\Oonepi}{$\mathcal{O}\left( 1+i \right)$}
\newcommand{\Ologn}{$\mathcal{O}\left( \log\left( n \right) \right)$}
\newcommand{\Onlogn}{$\mathcal{O}\left( n \log\left( n \right) \right)$}
\newcommand{\Oquad}{$\mathcal{O}\left( n^2 \right) $}

% Omega
\newcommand{\Omeganlogn}{$\Omega\left( n \log\left( n \right) \right)$}
\newcommand{\Omegalogn}{$\Omega\left( \log\left( n \right) \right)$}
\newcommand{\Omegan}{$\Omega\left( n \right) $}

% Theta
\newcommand{\Thetanlogn}{$\Theta \left( n \log (n) \right)$}
\newcommand{\Thetann}{$\Theta \left( n^2 \right)$}


\begin{document}
\noindent
\mbox{
    \begin{tcolorbox}[theme,tabularx={X||X|X},title=List
    Implementations,boxrule=0.5pt, width=.6\textwidth , box align=top]
        \rowcolors{2}{gray!25}{white} & \texttt{add(i,x)} \texttt{remove(x)} &
    \texttt{get(i)} \hspace{0.25in} \texttt{set(i,x)} \\
    \hline
        \texttt{ArrayStack}& \Onminusi$^A$  & \Oconst \\
        \texttt{ArrayDeque}$^A$ & \Oonepmin$^A$  & \Oconst \\
        \texttt{DualArrayDeque}$^A$ & \Oonepmin$^A$  & \Oconst \\
        \texttt{RootishArrayStack} & \Onminusi$^A$  & \Oconst \\
        \texttt{SLList} & \Oonepi & \Oonepi \\
        \texttt{DLList} & \Oonepmin & \Oonepmin \\
    \texttt{SEList} & % Ugh
    $\mathcal{O} \left( \frac{1 + \min \{ i, n-i \}}{b} \right)$$^A$ &%
    $\mathcal{O} \left( \frac{1 + \min \{ i, n-i \}}{b} \right)$$^A$ \\
        \texttt{SkipList} & \Ologn$^E$ & \Ologn$^E$ \\
    \end{tcolorbox}
}\hfill \mbox{
    \begin{tcolorbox}[theme,tabularx={X||X},title=Sorted Sets,boxrule=0.5pt, box
    align=top, width=0.35\textwidth]
        & Anything \\
    \hline
        \texttt{SkipList}$^r$ & \Ologn \\
        \texttt{Treap}$^r$ & \Ologn \\
        \texttt{ScapegoatTree} & \Ologn \\
        \texttt{2-4 Tree} & \Ologn \\
        \texttt{RB Tree} & \Ologn \\
    \end{tcolorbox}
}

\vspace{0.125in}
\noindent
% Newline, start the next set of tables
\mbox{
    \begin{tcolorbox}[theme,tabularx={X||l|l},title=USet
    Implementations,boxrule=0.5pt, box align=top, width=0.42\textwidth]
        & \texttt{add(x)} \texttt{remove(i)} & \texttt{find(x)} \\
    \hline
        \texttt{ChainedHashTable} & \Oconst$^{A,E}$ & \Oconst$^{E}$ \\
        \texttt{LinearHashTable} & \Oconst$^{A,E}$ & \Oconst$^{E}$ \\
    \end{tcolorbox}
}\hfill \mbox{
    \begin{tcolorbox}[theme,tabularx={X||l|X|X},title=Priority Queue
    Implementations,boxrule=0.5pt, box align=top, width=0.53\textwidth]
        & \texttt{findMin} & \texttt{deleteMin()} & \texttt{merge()} \\
    \hline
        \texttt{BinaryHeap}$^A$ & \Oconst & \Ologn & N/A \\
        \texttt{MeldableHeap}$^R$ & \Oconst & \Ologn & \Ologn \\
    \end{tcolorbox}
}

\noindent
\begin{center}
  \begin{tcolorbox}[theme,tabularx={X||X|X|X|X},title=Sorting
    Algorithms,boxrule=0.5pt, width=0.9\textwidth]
    & \multicolumn{3}{c|}{Time Complexity} & Space
    Complexity \\
    \cline{2-5}
    & Best & Average & Worst & Worst \\
    \hline
    \texttt{Quicksort} & \Omeganlogn & \Thetanlogn & \Oquad & \Ologn \\
    \texttt{Mergesort} & \Omeganlogn & \Thetanlogn & \Onlogn & \Oconst \\
    \texttt{Heapsort} & \Omeganlogn & \Thetanlogn & \Onlogn & \Oconst \\
    \texttt{Insertion Sort} & \Omegan & \Thetann & \Oquad & \Oconst \\
    \texttt{Selection Sort} & $\Omega (n^2)$ & \Thetann & \Oquad & \Oconst \\
    \texttt{Radix Sort} & $\Omega (nk)$ & $\Theta (nk) $ & $\mathcal{O} \left(
      nk
    \right)$ & $\mathcal{O}\left( n+k \right)$\\
    \end{tcolorbox}

\end{center}

\begin{tabularx}{\textwidth}{XXX}
  $A$ denotes an amortized runtime
  & $R$ denotes a randomized runtime
  & $E$ denotes an expected runtime
\end{tabularx}

\vfill {\hfill\scriptsize C. Bradley, 2018}
\end{document}