Differences between version 3 and predecessor to the previous major change of BigOhNotation.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 3 | Last edited on Sunday, August 24, 2003 8:03:15 am | by AristotlePagaltzis | Revert |
| Older page: | version 2 | Last edited on Monday, August 11, 2003 2:07:24 pm | by JohnMcPherson | Revert |
@@ -1,14 +1 @@
-BigOhNotation is a way of describing the cost of an [Algorithm] or block of code. It describes the element of the algorithm that, as it increases, has the largest effect upon the overall cost of the algorithm or equation.
-
-A mathematical example would be:
- 5n^2 + 6n - 2
-
-This is O(n^2) because the part of the equation that has the largest overall effect on the value of the equation is the n^2 component. The 5, being constant, is
-basically disregarded.
-
-Obviously, when writing code one should be aware of these concepts. Iterating over an array of items is O(n), iterating over the same array again within the first
-loop (say, to check for dupes) becomes O(n^2), and so on. Hash lookups are in general O(1).
-
-See http://www.cs.strath.ac.uk/~mdd/teaching/alg&comp/big_oh.html
-
-Some typically used orders are O(1), O(log N), O(N), O(N log N), O(N^2), in increasing cost.
+DeleteMe
