Merge pull request #1164 from jxu/patch-12

jakobkogler · web-flow · commit 97a9cca59aff · 2023-10-14T10:25:43.000+02:00
Ternary search: minor fix time complexity
diff --git a/src/num_methods/ternary_search.md b/src/num_methods/ternary_search.md
@@ -45,7 +45,7 @@ If $m_1$ and $m_2$ are chosen to be closer to each other, the convergence rate w
 
 ### Run time analysis
 
-$$T(n) = T({2n}/{3}) + 1 = \Theta(\log n)$$
+$$T(n) = T({2n}/{3}) + O(1) = \Theta(\log n)$$
 
 It can be visualized as follows: every time after evaluating the function at points $m_1$ and $m_2$, we are essentially ignoring about one third of the interval, either the left or right one. Thus the size of the search space is ${2n}/{3}$ of the original one. 
 
