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}