YouTube

Got a YouTube account?

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

English subtitles

← 01-21 Counting Steps

Get Embed Code
2 Languages

Showing Revision 1 created 06/27/2012 by Amara Bot.

  1. All right. Let's try another little quiz, but this one is going to move our understanding
  2. forward a little bit more. Here's a little bit of Python code.
  3. A subroutine called "countdown" takes an input x.
  4. It executes a statement, and then it goes into a while loop
  5. and repeats these two statements some number of times.
  6. Then when it's all done, it does one more statement.
  7. We can take for any given input--like this print countdown 50--
  8. we could count up the time--the number of statements executed--
  9. for this to execute. It's going to be something like this.
  10. We didn't talk about the number of steps that it take to do a print statement if there's a subroutine,
  11. but we're going to call it one for the print statement plus
  12. however many steps it takes to execute the subroutine call.
  13. In these case, countdown 50--what is it going to do?
  14. There's going to be 1 call there, 2 for each time that it counts down,
  15. which is going to be--what--10 times, right?
  16. It starts off at 50, going to go down by 5s until it hits 0.
  17. There is going to be 10 times that it's executing these two statements.
  18. That's 20--21, 22, and the print statement is 23.
  19. This--if we ask the time that this takes--is going to be 23 units.
  20. Here's the trickier question.
  21. What if we just say we don't know what n is. Someone is going to tell us n later.
  22. We're like to know the number of steps, the amount of time that it takes to execute this formula,
  23. as a function of n.
  24. We can't automatically grade a mathematical function--or maybe we can.
  25. The way that we're going to score this quiz is instead
  26. of you telling me a mathematical expression for this function,
  27. I want you to actually give me a function that takes as input n
  28. and produces as output the number of time steps that it will take to execute
  29. countdown or this entire block of code here.
  30. We already figured out what happens when n is 50, but we want a general form of this.