diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-10 11:36:09 -0400 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-10 11:36:09 -0400 |
commit | 930494e488c830bf43205bf6740bf7070183e51a (patch) | |
tree | 259d6e9960b421f47d29242d838cf01ccab71041 /mgr.tex | |
parent | eff3127564b01fd4162f8d4e55540ea570da2b7e (diff) |
Add shortcut for optimal query problem times
Diffstat (limited to 'mgr.tex')
-rw-r--r-- | mgr.tex | 4 |
1 files changed, 2 insertions, 2 deletions
@@ -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} |