YouTube

Got a YouTube account?

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

English subtitles

← 02-13 Running Time Vs Structure

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. As we've already seen for the algorithm that Alice was using, the running time of an algorithm
  2. can often very dramatically vary with the size of the input that the algorithm has given,
  3. but the running time can also change with the content or the structure of the input.
  4. And here's the simple example to show you this.
  5. So the algorithm takes as input a string s(0) to s(n-1), which means it's a string of length n,
  6. so n characters in the string and here's the algorithm.
  7. So the algorithm does something very simple given that string.
  8. It counts the number of times that the character a appears in that string.
  9. So it sets the counter to zero and then goes through all the characters in the string one by one.
  10. And if that character is equal to a then it will increase the counter.
  11. So as in the previous examples, we're going to take this line here as a simple operation
  12. meaning to take one time step each time it's executed.
  13. And we're also going to consider this one here as simple operation
  14. meaning also this whole line here is going to take one time step each time it's executed.
  15. Now, what I would like you to do as our next quiz is tell me the number of time steps
  16. this algorithm takes for a given string s.
  17. And to give you that answer, there are two things you need to know or two variables
  18. you have to take into account.
  19. One is n, the length of the string, and the other one as you're going to find out is a,
  20. and with a, we're just going to denote the number of times that
  21. the character a actually appears in that string.
  22. So your answer is going to be some formula that includes n and includes a,
  23. and I would like you to give me the running time by entering the coefficients in the following formula
  24. so it's going to be some number multiply by n plus some number multiply by a plus a constant.
  25. Please enter those two numbers. So not the result of the formula.
  26. It's the running time of this algorithm when it encounters a string of length n
  27. where the letter a occurs exactly a times.