m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-10 11:36:09 -0400
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-10 11:36:09 -0400
commit930494e488c830bf43205bf6740bf7070183e51a (patch)
tree259d6e9960b421f47d29242d838cf01ccab71041
parenteff3127564b01fd4162f8d4e55540ea570da2b7e (diff)
Add shortcut for optimal query problem times
-rw-r--r--definitions.sty1
-rw-r--r--mgr.tex4
2 files changed, 3 insertions, 2 deletions
diff --git a/definitions.sty b/definitions.sty
index 21ba74c..cbe36f2 100644
--- a/definitions.sty
+++ b/definitions.sty
@@ -15,5 +15,6 @@
}
\newcommand{\qptime}[2]{$\langle$#1, #2$\rangle$}
+\newcommand{\qpoptimal}{\qptime{$O(n)$}{$O(1)$}}
\newcommand{\definedterm}[1]{\emph{#1}}
diff --git a/mgr.tex b/mgr.tex
index 8929626..c13ccc1 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -206,7 +206,7 @@ serve as examples and because we will be using them in our algorithm.
ancestor.
}
-\textcite{tarjan1984} were the first to show an optimal \qptime{$O(n)$}{$O(1)$}
+\textcite{tarjan1984} were the first to show an optimal \qpoptimal{}
algorithm for LCA. \textcite{schieber1988} used a similar approach but
simplified the indexing structure, keeping the same time complexities.
\textcite{berkman1993} showed a completely new approach to the problem, which
@@ -224,7 +224,7 @@ problems.
element in the subarray $A[i, j]$.
}
-As mentioned above, \textcite{bender2000} show an \qptime{$O(n)$}{$O(1)$}
+As mentioned above, \textcite{bender2000} show an \qpoptimal{}
algorithm for the RMQ problem.
\subsection{Word infix regular queries}