## Got a YouTube account?

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

## ← 02-09 Big-Theta

• 1 Follower
• 27 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=2eFySdh2sWE" data-team="udacity"></div> ``` 2 Languages

Showing Revision 1 created 07/07/2012 by Amara Bot.

1. In that last analysis of grid graphs,
2. we ended up discovering that the number of edges is 2n - 2√n,
3. which is such a terrible function, but the fact of the matter is
4. as these analyses get more and more complicted
5. getting detailed answers like this is more and more cumbersome.
6. Researchers have worked out a scheme for talking about functions in a much more
7. high level way while still being completely rigorous but without it getting bogged down
8. in all the details, and this is the notion of asymptotic growth.
9. You may have heard it described in the form of Big Oh notation,
10. and we're going to get to Big Oh in a moment, but we need to start off with Big Theta.
11. Θ(g(n)) is actually a set of functions, specifically the set of functions that grow
12. equally quickly as g(n).
13. To be a bit more formal about it, we say that some function f(n) is in the set
14. of functions equally fast growing as g(n),
15. if and only if there are some constants c1 and c2 and some threshold n0
16. such that for any n bigger than n0, we have something that looks like this--
17. the function f(n) for all these values of n--all these big values of n--
18. is sandwiched between c1 * g(n) and c2 * g(n).
19. To illustrate this idea with a picture imagine we have some function f(n).
20. It grows. As n gets bigger, f(n) gets bigger.
21. We also have some function g(n) that we can multiply by c1 or we can multiply
22. by some bigger number c2.
23. What we find is that once we get out to the right of some threshold n0
24. f(n) is always between c2g(n) and c1g(n).
25. In the beginning maybe weird things happen, but once we get out far enough asymptotically
26. in the limit as things get really big, f(n) lies between c2g(n) and c1g(n).
27. If that's the case, if such c1, c2, and n0 exist, then we can say that f(n) is in Θ(g(n)).