Basically how do you find out which could be your worst or best case and any other "edge" cases you might have BEFORE having them and so, how do you prepare your code for them?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
migrated from stackoverflow.com May 1 '11 at 7:47
This question came from our site for professional and enthusiast programmers.
Based on the content of the algorithm you can identify what data structures/types/constructs are used. Then, you try to understand the (possible) weak points of those and try to come up with an execution plan that will make it run in those cases.
For example, the algorithm takes a string and an integer as input and does some sorting of the characters of the string.
Here we have:
String with some known special cases:
Integer with known special cases:
Sort algorithm that could fail in the following boundary cases:
Then, take all these cases and create a long list trying to understand how they overlap. Ex:
Now create test cases for them :)
Short summary: break the algorithm in basic blocks for which you know the boundary cases and then reassemble them, creating global boundary cases
I don't think there is any algorithm to determine edge conditions....just experience.
Example: for a byte parameter you would want to test numbers like 0, 127, 128, 255, 256, -1, anything that can cause trouble.
An "edge" has two meanings, and both are relevant when it comes to edge cases. An edge is either an area where a small change in the input leads to a large change in the output, or the end of a range.
So, to identify the edge cases of an algorithm, I first look at the input domain. Its edge values could lead to edge cases of the algorithm.
Secondly, I look at the output domain, and look back at the input values that might create them. This is less commonly a problem with algorithms, but it helps find problems in algorithms that are designed to generate output which spans a given output domain. E.g. a random-number generator should be able to generate all intended output values.
Finally, I check the algorithm to see if there are input cases which are similar, yet lead to dissimilar outputs. Finding these edge cases is the hardest, because it involves both domains and a pair of inputs.
This is a very general question so all I can do is throw out some general, vague ideas :)
-Examine boundary cases. Ex. if you're parsing a string what happens if the string is empty or null? If you're counting from x to y what happens at x and y?
Part of the skill of using algorithms is knowing their weaknesses and patholigical cases. Victor's answer gives some good tips, but in general I would advise that you need to study the topic in more depth to get a feel for this, I don't think you can follow rules of thumb to answer this question fully. E.g. see Cormen, or Skiena (Skiena in particular has a very good section on where to use algorithms and what works well in certain cases, Cormen goes in to more theory I think).