English subtitles

← 11-11 Number Of Instances

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. But first of all, let's play a little bit more with the numbers.
  2. Let's say I make the following table here.
  3. This is the number of instances you need to solve--say 1, 100, 10,000 and this is
  4. the size of the instances, and this is the size of the instances, so smaller than 10, smaller than 20,
  5. smaller than 30 or larger than 100.
  6. And now let's say you have algorithm that has running time 2^n.
  7. We'll simplify this here, so as the running time is 2^n, no O off, no polynomial involved.
  8. All I want you to get here is a filling full of numbers.
  9. Now, what I would like you to think about is in which case you see a brute force
  10. would be something to try out.
  11. If you think that you should try brute force either you're sure about it
  12. or it's at least something to think about, then I would like you to make a check mark
  13. in these boxes here and otherwise, leave the box blank, and of course, this is very subjective.
  14. If we don't agree, just click next and let's discuss where we don't agree.