• Managing your videos in Amara teams just got easier! Read about it in our latest blog post. Hide

## ← 13-09 Time Complexity Question

• 1 Follower
• 14 Lines

Unit 13 09 Time Complexity Question.mp4

### 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=8k25hH7DifE" data-team="udacity"></div> ``` 2 Languages

Showing Revision 1 created 11/28/2012 by Amara Bot.

1. Now we know we have an algorithm that can solve any game tree,
2. that can propagate the terminal values back up to the top
3. and tell us the value for any position.
4. It's theoretically complete, but now we need to know
5. the complexity of the algorithm to figure out if it's practical.
6. Let's look at an analysis of how long it's going to take.
7. Let's say that the average branching factor--
8. the number of possible moves or actions coming out of a position--is b.
9. Here b would be 4.
10. And let's say that the depth of the tree is m, so b wide and m deep.
11. Now what I want you to tell me is what would be the computational complexity
12. of searching through all the paths and backing the values up to the top.
13. Would it be of the order of b times m or the order of be to the mth power
14. or the order of m to the b power? Chose one of these.