English subtitles

← Predicting Run Time Solution - Intro to Computer Science

Get Embed Code
2 Languages

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.