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:

    The writer who aims at producing the platitudes which are “not for an age, but for all time” has his reward in being unreadable in all ages.... The man who writes about himself and his own time is the only sort of man who writes about all people and about all time.
    George Bernard Shaw (1856–1950)