subquadratic

• 線形($O(n)$)より大きく、二次($O(n^2)$)より小さい実行時間で動作するアルゴリズムを指す
• $O(n^{2/logn})$とか, $O(n^{1.5})$など

数学的な定義

• subquadratic関数は、以下の不等式を満たす関数$\phi$である。 $\phi (x+y)+\phi (x-y)\le 2\phi (x)+2\phi (y)$
• $\phi (x)=x^2$ のとき、等号で成立する
• 不等号が逆$\ge$になる場合は、superquadraticと呼ばれる

関連

• 計算量

参考

https://www.degruyter.com/document/doi/10.1515/dema-2006-0405/pdf