1 00:00:00,000 --> 00:00:05,000 Removing any of these subsets will result in a passing test, 2 00:00:05,000 --> 00:00:11,000 which means that we again have to increase the granularity by doubling n in here. 3 00:00:11,000 --> 00:00:14,000 Now we split the input into six subsets, 4 00:00:14,000 --> 00:00:18,000 resulting in six more attempts to remove individual parts-- 5 00:00:18,000 --> 00:00:20,000 all of them will pass -- 6 00:00:20,000 --> 00:00:23,000 and then we have to increase the granularity again, which would be 12. 7 00:00:23,000 --> 00:00:26,000 But now our input only has 8 characters, 8 00:00:26,000 --> 00:00:29,000 and we can't split an 8 character input into 12 subsets 9 00:00:29,000 --> 00:00:32,000 unless these subsets would be empty. 10 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. 11 00:00:36,000 --> 00:00:40,000 We make sure that n cannot grow beyond the size of the input, 12 00:00:40,000 --> 00:00:43,000 which means that in our case n would now be 8. 13 00:00:43,000 --> 00:00:46,000 This is the final stage of delta debugging 14 00:00:46,000 --> 00:00:50,000 where it tries to remove one character after another, 15 00:00:50,000 --> 00:00:53,000 but all of these removals result in passing test cases, 16 00:00:53,000 --> 00:00:56,000 so what we get in the end is this very string 17 00:00:56,000 --> 00:01:00,000 and we have now shown that every single character in here 18 00:01:00,000 --> 00:01:06,000 is relevant, because removing it changes the outcome of a test from fail to pass. 19 00:01:06,000 --> 00:01:10,000 So, what delta debugging gives us in the end is an input --a simplified input-- 20 00:01:10,000 --> 00:01:13,000 where every single part is relevant. 21 00:01:13,000 --> 00:01:18,000 At this point you may wonder how many tests does delta debugging actually take? 22 00:01:18,000 --> 00:01:21,000 You can see that at the very end when every single character has 23 00:01:21,000 --> 00:01:24,000 to be removed individually, the number of tests of course 24 00:01:24,000 --> 00:01:28,000 is proportional to the length of the simplified input. 25 00:01:28,000 --> 00:01:32,000 In the worst case--that is, for very pathological examples-- 26 00:01:32,000 --> 00:01:36,000 the complexity of delta debugging is squared with respect to its input. 27 00:01:36,000 --> 00:01:39,000 However, there is a nice situation in which delta debugging 28 00:01:39,000 --> 00:01:44,000 simply becomes a binary search and is as efficient as a binary search. 29 00:01:44,000 --> 00:01:48,000 So, when does delta debugging need a logarithmic number of tests? 30 00:01:48,000 --> 00:01:50,000 Is this when all tests fail? 31 00:01:50,000 --> 00:01:55,000 Is this when there is always 1/2 that can be removed and fails? 32 00:01:55,000 --> 00:01:58,000 Is this when all tests pass? 33 00:01:58,000 --> 00:02:01,013 Or is this never? Check all that apply.