Editing Time complexity (section)

== Polylogarithmic time ==
An algorithm is said to run in '''[[polylogarithmic function|polylogarithmic]] time''' if its time <math>T(n)</math> is <math>O\bigl((\log n)^k\bigr)</math> for some constant {{mvar|k}}. Another way to write this is <math>O(\log^kn)</math>.

For example, [[Matrix chain multiplication|matrix chain ordering]] can be solved in polylogarithmic time on a [[parallel random-access machine]],<ref>{{cite journal | last1 = Bradford | first1 = Phillip G. | last2 = Rawlins | first2 = Gregory J. E. | last3 = Shannon | first3 = Gregory E. | doi = 10.1137/S0097539794270698 | issue = 2 | journal = [[SIAM Journal on Computing]] | mr = 1616556 | pages = 466–490 | title = Efficient matrix chain ordering in polylog time | volume = 27 | year = 1998}}</ref> and [[Graph (discrete mathematics)|a graph]] can be [[Planarity testing|determined to be planar]] in a [[Dynamic connectivity|fully dynamic]] way in <math>O(\log^3n)</math> time per insert/delete operation.<ref>{{cite conference | last1 = Holm | first1 = Jacob | last2 = Rotenberg | first2 = Eva | editor1-last = Makarychev | editor1-first = Konstantin | editor2-last = Makarychev | editor2-first = Yury | editor3-last = Tulsiani | editor3-first = Madhur | editor4-last = Kamath | editor4-first = Gautam | editor5-last = Chuzhoy | editor5-first = Julia | editor5-link = Julia Chuzhoy | arxiv = 1911.03449 | contribution = Fully-dynamic planarity testing in polylogarithmic time | doi = 10.1145/3357713.3384249 | pages = 167–180 | publisher = Association for Computing Machinery | title = Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 | year = 2020| isbn = 978-1-4503-6979-4 }}</ref>