• The Amara On Demand team is looking for native speakers of German, Japanese, Korean, Italian, Hindi and Dutch to help with special paid projects
Apply here 非表示にする

## ← 18-24 Expected Running Time

• 1 フォロワー
• 15 Lines

### 埋め込みコードを取得する 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=mJ1yLNMV1SQ" data-team="udacity"></div> ``` 1言語

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

1. And the exact analysis of this algorithm here reveals that if the Boolean formula
2. has a satisfying assignment, then this assignment is found where the probability of about
3. 3/4^n times some polynomial of n and I'll just write that as p(n) here.
4. So how many times do you have to run this algorithm given the success probability here
5. to find the satisfying assignment on average, assuming there exist one.
6. Now, if you have had a basic statistics course, you should already know
7. that the expected running time, so how often we have to run this algorithm until we find
8. a satisfying assignment assuming the Boolean formula has one is the time
9. for a single run divided by the success probability of one run.
10. And of course, I'm going to let you figure our the final answer for this as our next quiz.
11. So is the expected running time O(3/4^n times the polynomial of n) which is this polynomial here
12. times some other polynomial, which will represent the time for one run of this algorithm here
13. or is it O(4/3^n times the polynomial of n) times the time required for this algorithm here,
14. or is it O(3/4^n times the polynomial for this algorithm here) divided by this polynomial here,
15. or finally, is it O(4/3^n times the time required to run this algorithm here) divided by this polynomial.