YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 18-27 Big O Solution

Get Embed Code
1 Language

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

  1. And of course, this is a bit of a nitpicker question but it equals O(1.3c₄^n*n to some constant)
  2. and the reason being is that 4/3 is equal to 1.3333, of course, this goes on infinitely,
  3. and for O notation to be correct, of course, you have to round up,
  4. no matter what the digit is that you're rounding.
  5. So the expected running time for this algorithm here is actually exponential in n.
  6. Now, you might be asking--well, okay, so we know that three SAT is solvable in exponential time,
  7. now we introduce randomness, which means we're not even sure that we're finding
  8. the satisfying assignment, at least not totally sure, and we're still ending up
  9. with exponential running time, so what's the deal here.