For Linear Time
An algorithm that runs in O(n), or linear, time has a very natural property:its running time is at most a constant factor times the size of the input. One basic way to get an algorithm with this running time is to process the input in a single pass, spending a constant amount of time on each item of input encountered. Other algorithms achieve a linear time bound for more subtle
reasons.
For O(n log n) Time
It is the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time.
For Quadratic time arises naturally from a pair of nested loops: An algorithm
consists of a loop with O(n) iterations, and each iteration of the loop
launches an internal loop that takes O(n) time. Multiplying these two factors
of n together gives the running time.
An algorithm that runs in O(n), or linear, time has a very natural property:its running time is at most a constant factor times the size of the input. One basic way to get an algorithm with this running time is to process the input in a single pass, spending a constant amount of time on each item of input encountered. Other algorithms achieve a linear time bound for more subtle
reasons.
For O(n log n) Time
It is the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time.
For Quadratic time arises naturally from a pair of nested loops: An algorithm
consists of a loop with O(n) iterations, and each iteration of the loop
launches an internal loop that takes O(n) time. Multiplying these two factors
of n together gives the running time.
No comments:
Post a Comment