We're going to see many many examples going forward, but let's finish up with a couple of examples from programs that we've already seen. For example the Gambler's ruin, so how long is it going to take to compute the chance of doubling a million dollars, betting a dollar at a time? Again, to figure this out we put in the timing code in red in there that estimates how long our program runs for given a dollar amount, and we can just run it. So, this is for doubling $1,000, and now we do a 100 trials to damp out the possibility of other things going on in the computer and also to get a more accurate probabilistic estimate. So, we're doing a 100 trials. We run it again and we compute and we double to $ 2,000 in 2,000 experiments, and then we compute the running time in the ratio, then we double to $4,000 which is our initial stake. Compute the running time in the ratio, and as we go we noticed that the ratio of running time seems to be about four and that coincides with our math model that we talked about since the running time should be proportional to N squared, and now we have a running time for significant large value of N that is going to kstabilize and tell us what the constant is on the particular machine we're using, and we can just use the constant four to extrapolate to the next higher values and to get to a million that's four to the sixth, and so it comes back to the same result, 4.8 million seconds to run this program for a million. It's about two months, so maybe we have two months or maybe we want to work with some smaller number but we have some understanding of how this program is running, and we can use it to quickly predict what the running time is. So, here's just another simple example. It's the same thing. Suppose we have these observations, now our ratios are all four, and if we want to get for 64,000 we just keep multiplying by two, to get this 64,000 keep multiplying the time by four, and then we get to 20,000 seconds, and then what's the order of growth? Well, that ratio is two to the B if the order of growth is N to B, so in this case B is two, so it's going to be N squared. Just take the binary log of that ratio and that gives the order of growth. So that's an example of simply running the experiments, doing the extrapolation and learning the order of growth from the ratios. What about coupon collector? How long does it take to simulate collecting a million coupons? Again, we just add the timing same way as before, find the time before we start, find the time after we're done, and run it for different numbers of gift coupons. So now we have to run it for a pretty high number of coupons to get something interesting. Sets 125,000 takes seven seconds, 250,000 takes 14, 500,000 takes 31, the ratio is looking like two, so that means to do a million, well, we just double it, and so it takes about a minute to simulate coupon collector for a million coupons. Again, the math model says it should be about N log N, so that matches with the doubling ratio B two because it's only the exponent of N that matters. So these programs, the gambler and coupon collector look quite similar in many ways, their experimental results, but with the doubling test we can very quickly get some understanding of their performance which is quite different. So, about one minute to do a million coupons. Now, in this case you're going to run out of memory before you run out of time, and I should mention that another thing that we often have to do is analyze memory requirements because, as in this example, program might take a lot of memory. So, that is very system dependent but we can, for Java programs usually come up with a decent estimate of the memory requirements of a program. So, the basic unit of memory is a bit but actually in Java it's a byte, the smallest addressable unit, that's eight bits. In your computer, maybe it has a gigabyte or about a billion bytes, ancient computers had a megabyte or about a million bytes. Then you just have to know for each primitive data type how many bytes are used to represent a data type value, and actually in Java Boolean even though you think it should be one bit, it actually uses a whole byte, a char uses two bytes, it's in unicode 16 bits, and int uses four, float also uses four, long uses eight, double uses eight and so forth. Then data structures depends on the system, you have to do some experiments with your own programs but typical array of an int is going to use 4N plus 16 bytes or for doubles is 8N plus 16, so its eight bytes for each double plus some overhead to handle the array, and then if you use multiple dimensional arrays then we can use the tilde to really it's efficient in terms of an N by N array, it's got N squared things and if each one of them or take four bytes, it's about 4N squared bytes and so forth. String has higher overhead and you can work it out for different systems. So, for example a 2,000 by 2,000 double array uses about 32 megabytes, and you can do these kinds of estimates if you have programs that start to use significant amounts of memory. So, the summary is you can use experiments, you can use mathematical analysis, and the scientific method, and the simple doubling experiment approach that we discussed to figure out whether your program might be useful to solve a large problem. If it's not fast enough then you might want to buy a new computer and solve bigger problems, that is if it scales. That is it is running time N log N or N. If it doesn't scale then you got to look for a better algorithm. Maybe there's one out there and if you find one then you can go back and iterate this process, and if it does scale then you're fine. If you can't find one, well, maybe you could invent a better algorithm that's worthy thing to think about anyway, because there's many more problems than we know algorithms for solving. For example, we don't know how to solve the three sum problem as efficiently as we'd like. We can solve it in square but not less than that. So that's a basic summary, and just the particular case in point, it wasn't that long ago there were two computer science grad students at Stanford that had a program to index and rank everything on the web so as to enable search on the web. For a while, they were doing pretty well with that by buying a new computer solving bigger problems, but they weren't quite at the point where they're changing the world, so what they did was invent a better algorithm and iterate the process for a while. That algorithm is known as PageRank and it's discussed in the book, and those grad students where Larry Page and Sergey Brin and that led to Google which certainly has had a major impact on the world, and the lesson of this is that performance really does matter if you're going to address a large problem.
