Problem size: Difference between revisions

Content deleted Content added

Inline

Revision as of 10:28, 23 September 2002

See "what links here" to see where this came from.

This is often loosely defined. AKA input size, it means in english: "whatever it is that you are putting into the algorithm".

In order for you to get an accurate analysis of an algorithm, you need to define your input to be as atomic as possible, and if not, then, state the reasons for your doing so. Example:

If your input is N binary trees, sometimes it might be useful to not include the computational cost of generating those trees in the first place, eg, they were pre-generated, and it requires O(1) or a constant time, to simply read them from memory. However, it might be more worth it to include the cost of generating the trees if you are spending every 10 minutes re-generating them.

These above two example actually show a contrast in approach to analysis, that hint at the downfalls of the Big O notation when applied to increasingly complex (in terms of real world situations) environnments.

Stephen Wolfram

@@ Line 3: / Line 3: @@
 This is often loosely defined. AKA input size, it means in english: "whatever it is that you are putting into the algorithm".
-In order for you to get an accurate Big O notation, you need to try and get your input to be as atomic as possible, and if not, then, state the reasons for your doing so. Example:
+In order for you to get an accurate [[analysis]] of an algorithm, you need to define your input to be as atomic as possible, and if not, then, state the reasons for your doing so. Example:
-If your input is N trees, sometimes it might be useful to not include the computational cost of generating those trees in the first place, eg, they were pre-generated at the dawn of time, and it requires O(1) or a constant time, to simply read them from memory. However, it might be more worth it to include the cost of generating the trees if you are spending every 10 minutes re-generating them.
+If your input is N binary trees, sometimes it might be useful to not include the computational cost of generating those trees in the first place, eg, they were pre-generated, and it requires O(1) or a constant time, to simply read them from memory. However, it might be more worth it to include the cost of generating the trees if you are spending every 10 minutes re-generating them.
-These above two example actually show some of the downfalls of the Big O notation when applied to increasingly complex (in terms of real world situations) envrinments.
+These above two example actually show a contrast in approach to analysis, that hint at the downfalls of the Big O notation when applied to increasingly complex (in terms of real world situations) environnments.
 [[Stephen Wolfram]]