English subtitles

← Number of Tests Solution - Software Debugging

Get Embed Code
3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. And now for the answer.
  2. Let's check each one by one.
  3. When all tests fail that's an interesting situation.
  4. It's rather unlikely, but let's assume this actually happens.
  5. Then we split the inputs initially into two separate sets,
  6. removing the first subset fails we proceed with this subset. N remains 2.
  7. And we do this again and we split again the input into two subsets
  8. and two subsets again and two two subsets again.
  9. This is exactly like binary search described by Kernighan and Pike,
  10. which is logarithmic.
  11. The next answer: where there always is a half that can be removed and fails,
  12. this is the same situation, expect that we may have to remove the first half first and getting a pass.
  13. But still in terms of complexity it's still logarithmic in proportion
  14. to the size of the input and therefore this is a nice situation
  15. in which delta debugging is very, very effective.
  16. This is actually one of the strings of delta debugging that if you can split the input
  17. into two halves and one of them fails, then it behaves like a binary search.
  18. By increasing the granularity later one,
  19. then it's no longer as efficient in the number of tests,
  20. but is very, very thorough by trying to remove small parts one after the other.
  21. It's like a binary search in the beginning--super efficient,
  22. and then it's as thorough as trying to remove every single part after another.
  23. When all tests pass, then delta debugging does not need a logarithmic number
  24. of tests. That's more like a linear number of tests.
  25. And never--that's not the case, because in these two situations,
  26. then indeed the number of tests is logarithmic.
  27. This is the answer.