Time Complexity - Sub-quadratic Time

Sub-quadratic Time

An algorithm is said to be subquadratic time if T(n) = o(n2).

For example, most naïve 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.

Read more about this topic:  Time Complexity

Famous quotes containing the word time:

    “I would rather be old for a shorter time than be old before my time.”
    —Michel de Montaigne (1533–1592)