Sub-Linear Time Algorithm

A Sub-Linear Time Algorithm is an algorithm that satisfies the time complexity defined as T(n) = O(n) or T(n) = O(n^½).

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

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time
  • QUOTE: An algorithm is said to run in sub-linear time (often spelled sublinear time) if T(n) = o(n). In particular this includes algorithms with the time complexities defined above, as well as others such as the O(n^½) Grover's search algorithm.

    Typical algorithms that are exact and yet run in sub-linear time use parallel processing (as the NC₁ matrix determinant calculation does), non-classical processing (as Grover's search does), or alternatively have guaranteed assumptions on the input structure (as the logarithmic time binary search and many tree maintenance algorithms do). However, formal languages such as the set of all strings that have a 1-bit in the position indicated by the first log(n) bits of the string may depend on every bit of the input and yet be computable in sub-linear time.

    The specific term sublinear time algorithm is usually reserved to algorithms that are unlike the above in that they are run over classical serial machine models and are not allowed prior assumptions on the input.

---