WEBVTT 00:00:00.000 --> 00:00:05.000 Removing any of these subsets will result in a passing test, 00:00:05.000 --> 00:00:11.000 which means that we again have to increase the granularity by doubling n in here. 00:00:11.000 --> 00:00:14.000 Now we split the input into six subsets, 00:00:14.000 --> 00:00:18.000 resulting in six more attempts to remove individual parts-- 00:00:18.000 --> 00:00:20.000 all of them will pass -- 00:00:20.000 --> 00:00:23.000 and then we have to increase the granularity again, which would be 12. 00:00:23.000 --> 00:00:26.000 But now our input only has 8 characters, 00:00:26.000 --> 00:00:29.000 and we can't split an 8 character input into 12 subsets 00:00:29.000 --> 00:00:32.000 unless these subsets would be empty. 00:00:32.000 --> 00:00:36.000 So we're going to fix this a bit by setting up this minimum function over here. 00:00:36.000 --> 00:00:40.000 We make sure that n cannot grow beyond the size of the input, 00:00:40.000 --> 00:00:43.000 which means that in our case n would now be 8. 00:00:43.000 --> 00:00:46.000 This is the final stage of delta debugging 00:00:46.000 --> 00:00:50.000 where it tries to remove one character after another, 00:00:50.000 --> 00:00:53.000 but all of these removals result in passing test cases, 00:00:53.000 --> 00:00:56.000 so what we get in the end is this very string 00:00:56.000 --> 00:01:00.000 and we have now shown that every single character in here 00:01:00.000 --> 00:01:06.000 is relevant, because removing it changes the outcome of a test from fail to pass. 00:01:06.000 --> 00:01:10.000 So, what delta debugging gives us in the end is an input --a simplified input-- 00:01:10.000 --> 00:01:13.000 where every single part is relevant. 00:01:13.000 --> 00:01:18.000 At this point you may wonder how many tests does delta debugging actually take? 00:01:18.000 --> 00:01:21.000 You can see that at the very end when every single character has 00:01:21.000 --> 00:01:24.000 to be removed individually, the number of tests of course 00:01:24.000 --> 00:01:28.000 is proportional to the length of the simplified input. 00:01:28.000 --> 00:01:32.000 In the worst case--that is, for very pathological examples-- 00:01:32.000 --> 00:01:36.000 the complexity of delta debugging is squared with respect to its input. 00:01:36.000 --> 00:01:39.000 However, there is a nice situation in which delta debugging 00:01:39.000 --> 00:01:44.000 simply becomes a binary search and is as efficient as a binary search. 00:01:44.000 --> 00:01:48.000 So, when does delta debugging need a logarithmic number of tests? 00:01:48.000 --> 00:01:50.000 Is this when all tests fail? 00:01:50.000 --> 00:01:55.000 Is this when there is always 1/2 that can be removed and fails? 00:01:55.000 --> 00:01:58.000 Is this when all tests pass? 00:01:58.000 --> 00:02:01.013 Or is this never? Check all that apply.