## ← 18-27 Big O Solution

• 1 Follower
• 9 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=7a9x_Y2_Plw" data-team="udacity"></div> ``` 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.