## ← Predicting Run Time Solution - Intro to Computer Science

• 2 Followers
• 40 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=HBwT29hWXrs" data-team="udacity"></div> ``` 2 Languages

• English [en] original
• Japanese [ja]

Showing Revision 5 created 05/25/2016 by Udacity Robot.

1. So here's the answer. We'll try it and see what we
2. get. And while it's running, let's think about what we should
3. get. So we can look at the examples that we did
4. so far and try to make some predictions. So we saw
5. when the value passed in was 10 to the 5, that
6. the time it took to execute was 0.005. When the time
7. passed in was 10 to the 6, so 1 million. We
8. saw that the time to execute was 0.05, and now we're trying
9. to predict 10 to the nine. If we look at
10. the pattern here, every time we increase n by a
11. factor of 10, the time also multiplies by a factor
12. of 10. And, that's not surprising because the loop is going
13. around ten more times. The times, number of times we
14. go through the loop, scales as a factor of the
15. input value n, so if we increase n by a
16. factor of 10, the time will also increase by a factor
17. of 10. And we see we have got our
18. result now, so if we increase by another factor
19. of 10, we would expect that this would also
20. increase, that it would take about half a second to
21. do 10 million. If we increased by another factor
22. of 10 we would expect the running time would
23. also multiple by 10, so we'd be up to
24. about 5 seconds. And if we increased by another factor
25. of 10 which is the billion that we tried, we'd
26. expect it to also increase by another factor of 10.
27. Getting to be something around 50 seconds. So it's not
28. exactly a 1,000 times what we had when we did
29. spin loop passing in a million, but it's pretty close
30. to that. Now it's taking almost a minute, 1,000 times
31. this would be 54 seconds, so it's a little bit
32. off from that. But very close, and if we tried it
33. a few more times, we might get a slightly different result.
34. Let's try is one more time. So we tried it again
35. and this time we got 55.89 seconds, pretty close to what
36. we got the previous time. The important point here is that
37. the running time depends on the value of the input to
38. spin loop and it depends on in a linear way. As
39. we increase the magnitude of n, the higher number of times
40. through the loop, the running time scales linearly with that value.