Subquadratic Time Algorithm

A Subquadratic Time Algorithm is an algorithm that satisfies the time complexity defined as T(n) = O(n²)

• Context:
  • It can (often) be applied to a Subquadratic Time Task.
• Example(s):
  • …
• Counter-Example(s):
  • Logarithmic Time.
  • Polylogarithmic Time.
  • Sub-Linear Time.
  • Linear Time.
• See: Logarithmic Time, Time Complexity, Sorting Algorithm, Polynomial Time Task.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Time_complexity#Sub-quadratic_time
  • QUOTE: An algorithm is said to be subquadratic time if T(n) = o(n²). For example, simple, comparison-based sorting algorithms are quadratic (e.g. insertion sort), but more advanced algorithms can be found that are subquadratic (e.g. Shell sort). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.

---