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 believe that all the survivors are mad. One time or another their madness will explode. You cannot absorb that much madness and not be influenced by it. That is why the children of survivors are so tragic. I see them in school. They don’t know how to handle their parents. They see that their parents are traumatized: they scream and don’t react normally.
    Elie Wiesel (b. 1928)