
Title:
Predicting Run Time Solution  Intro to Computer Science

Description:

So here's the answer. We'll try it and see what we

get. And while it's running, let's think about what we should

get. So we can look at the examples that we did

so far and try to make some predictions. So we saw

when the value passed in was 10 to the 5, that

the time it took to execute was 0.005. When the time

passed in was 10 to the 6, so 1 million. We

saw that the time to execute was 0.05, and now we're trying

to predict 10 to the nine. If we look at

the pattern here, every time we increase n by a

factor of 10, the time also multiplies by a factor

of 10. And, that's not surprising because the loop is going

around ten more times. The times, number of times we

go through the loop, scales as a factor of the

input value n, so if we increase n by a

factor of 10, the time will also increase by a factor

of 10. And we see we have got our

result now, so if we increase by another factor

of 10, we would expect that this would also

increase, that it would take about half a second to

do 10 million. If we increased by another factor

of 10 we would expect the running time would

also multiple by 10, so we'd be up to

about 5 seconds. And if we increased by another factor

of 10 which is the billion that we tried, we'd

expect it to also increase by another factor of 10.

Getting to be something around 50 seconds. So it's not

exactly a 1,000 times what we had when we did

spin loop passing in a million, but it's pretty close

to that. Now it's taking almost a minute, 1,000 times

this would be 54 seconds, so it's a little bit

off from that. But very close, and if we tried it

a few more times, we might get a slightly different result.

Let's try is one more time. So we tried it again

and this time we got 55.89 seconds, pretty close to what

we got the previous time. The important point here is that

the running time depends on the value of the input to

spin loop and it depends on in a linear way. As

we increase the magnitude of n, the higher number of times

through the loop, the running time scales linearly with that value.