The Big O Notation
The O() notation is a mathematical way of dealing with approximations. We say that the worst case time complexity of an algorithm is O(n2). It means, for n records, the time taken for the algorithm to run is in the order of square of n. We consider only higher orders while estimating time complexity. For example:
O(n2 + 2n) = O(n2)
The higher order dominates other values while n varies. Since we are eliminating lower order terms, one O(n2) algorithm can be much faster than another O(n2) algorithm.
- summary of Algorithm Speed, from The Pragmatic Programmer: from Journeyman to Master
The O() notation is a mathematical way of dealing with approximations. We say that the worst case time complexity of an algorithm is O(n2). It means, for n records, the time taken for the algorithm to run is in the order of square of n. We consider only higher orders while estimating time complexity. For example:
O(n2 + 2n) = O(n2)
The higher order dominates other values while n varies. Since we are eliminating lower order terms, one O(n2) algorithm can be much faster than another O(n2) algorithm.
- summary of Algorithm Speed, from The Pragmatic Programmer: from Journeyman to Master
No comments:
Post a Comment