| Contents [0/8] |
| Video [1/8] |
| Adding up an arithmetic series [2/8] |
| What if N=32? [3/8] |
| What if N=64? [4/8] |
| Adding up an geometric series [5/8] |
| What if N=32? [6/8] |
| What if N=64? [7/8] |
| RelativeGrowth [8/8] |
(Click here for one slide per page)
| Video [1/8] |
let's talk about adding stuff up suppose I have the numbers that I counted out zero one two three four five six and I go up to some bound in if I add all those up what do I get well let's count to sixteen so 1 then 2 then 3 then 4 and what I'm showing here is how many things there are at each value so if I add all of these things up it's gonna be the total size of this triangle so the number of numbers how many numbers did I write down well there's 16 16 15 15s this is something like the 12 days of Christmas there's 12 drummers drumming or whatever but for us we've got a triangle here and the important thing to notice about triangles is that they're half of a square so I can square off this triangle and what would I get in that case it's really obvious right so there'd be 16 counting this way 16 counting this way that's 16 squared I don't have the whole square here I only have half of it but that's approximately going to be N squared divided by 2 if you want to get picky about it n squared divided by twos off by a bit and why is that well if you check the whole square and cut it in half you have to decide what to do with this diagonal row so there's this diagonal going through and when we divide by 2 what we're gonna get is half of that diagonal so if you want to calculate what we're actually doing here you need to add in the other half so we've got half of the squared numbers plus we have to add in the other half of the diagonal which the half of squares left out but this is not really important when you're thinking with approximation the difference between N squared divided by 2 and this function here is going to be unimportant to we don't really care about these low ordered terms in a polynomial the reason is that we're thinking approximately and when we're fitting our curve we're only fitting with respect to the highest order polynomial so we want to pick a simple curve and that's the idea of approximate analysis or order of growth looking at this the sum may seem very reasonable so 16 versus 16 squared divided by 2 doesn't look that bad but let's suppose we wanted to count up to 32 what is this gonna look like oh lordy that's getting a bit much what if we want to count up to 64 or what's gonna happen oh gosh that's really sad I'm getting a lot of stuff and the point here is that the size of the triangle is growing with respect to the square of the number and so as we get bigger and bigger numbers we're going up a quadratic curve of growth and you can see visually here that is giving you a pretty big triangle even just for 64 let's try the same experiment using geometric growth I'm going to take the geometric series 1 2 4 8 16 etc and add up all the numbers let's try it for 16 so counting to 16 here what are we gonna do well there's one to Oh skip three we just have four oh we're good to skip five six and seven or eight oh it's a skip a lot it's going up to 16 okay so the total number of numbers here I don't know what is that okay so to interpret this you can think about flat packing these numbers so IKEA made its fortune by flat packing furniture we can make a fortune flat packing numbers the important observation here is that we can take all of the top rows except for the last one and we can sort of flat pack that on top of this row and get something that's just too deep so what does that look like we'll take the eights stick them there then just put the fours next door then put the twos then put the ones and there we are and note that we have one space left indeed this sum is approximately twice the upper bound so I lay down 16 numbers and then I can fit all of the previous ones just lying them on top so I have 16 plus 15 in this case and in general the sum of the numbers from 1 up to 2 to the K for any K it's 2 to the k plus 1 that's the next number the double number minus 1 I can apply this here to figure out what is the sum of the geometric series going up to 16 well 16 is of course 2 to the 4th power so how many numbers do I get well that would be 2 to the 5th power minus 1 so what's 2 to the 5th power that's 32 minus 1 31 so we've got 31 numbers I'm pointing out this precise equation because it's going to be important in your systems classes but actually we're not going to care about it here the important thing for us is that when you look at the sum of the geometric series up to n it's gonna be approximately 2 in now you may not be impressed by this because this doesn't look that different than it looked for arithmetic series you're like yeah it's a little smaller don't care what if we go to 32 what does it look like oh look it's only got one extra line remember when I computed the sum the arithmetic series I ended up with 16 more lines when I did this I can flat pack this down and I've just got 32 plus 31 and I'm done what about 64 well that's not so bad either I mean it's kind of Scrolls over but it's certainly nothing like we had a minute ago if you go back to where we were I find it very effective to think about these sums visually when I look at this sum it looks really really big and when I look at this sum it seems a lot smaller if you want to see just the numbers we can do that too let's take T 2 to be the sum of the geometric series that's multiplying by 2 up to n let P 1 be the sum of the arithmetic series I pick T for x and P 4 plus so we're going by plus 1 here and by x 2 there and what have we got for different input sizes and it's nice look at about a million you get 2 million for the geometric sum and that's what you expect because you're getting about double look what happens with the quadratic result here we're getting for the arithmetic sum this is indeed half a million squared which is about 500 trillion and 500 trillion is generally speaking a number I try to avoid so why am I going on and on and on about these two sums well it turns out that these are of huge practical importance in computing as we'll see when we start to look at resizing arrays |
| Adding up an arithmetic series [2/8] |
Suppose we add up the elements we get counting by adding 1:
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N
Let's count to 16!
01 02 02 03 03 03 04 04 04 04 05 05 05 05 05 06 06 06 06 06 06 07 07 07 07 07 07 07 08 08 08 08 08 08 08 08 09 09 09 09 09 09 09 09 09 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16
You get a triangle, which is half of a square.
The sum is approximately N squared divided by 2.
0 + 1 + 2 + 3 + 4 + ... + N = (N^2)/2 + N/2
Why add N/2?
(N^2)/2 only includes half of the diagonal
| What if N=32? [3/8] |
Suppose we add up the elements we get counting by adding 1:
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N
Let's count to 32!
01 02 02 03 03 03 04 04 04 04 05 05 05 05 05 06 06 06 06 06 06 07 07 07 07 07 07 07 08 08 08 08 08 08 08 08 09 09 09 09 09 09 09 09 09 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32
| What if N=64? [4/8] |
Suppose we add up the elements we get counting by adding 1:
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N
Let's count to 64!
01 02 02 03 03 03 04 04 04 04 05 05 05 05 05 06 06 06 06 06 06 07 07 07 07 07 07 07 08 08 08 08 08 08 08 08 09 09 09 09 09 09 09 09 09 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 46 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 53 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 54 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 56 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 58 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64
| Adding up an geometric series [5/8] |
Suppose we add up the elements we get counting by multiplying 2:
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + ... + N
Let's count to 16!
01 02 02 04 04 04 04 08 08 08 08 08 08 08 08 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16
The last element is so large that all the prior elements can be placed on top without overlapping
This is like flat packing
08 08 08 08 08 08 08 08 04 04 04 04 02 02 01 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16
The sum is approximately 2 times N.
1 + 2 + 4 + 8 + ... + 2^k = 2^(k+1) - 1
| What if N=32? [6/8] |
Suppose we add up the elements we get counting by multiplying 2:
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + ... + N
Let's count to 32!
01 02 02 04 04 04 04 08 08 08 08 08 08 08 08 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32
Flat packing:
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 08 08 08 08 08 08 08 08 04 04 04 04 02 02 01 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32
| What if N=64? [7/8] |
Suppose we add up the elements we get counting by multiplying 2:
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + ... + N
Let's count to 64!
01 02 02 04 04 04 04 08 08 08 08 08 08 08 08 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64
Flat packing:
32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 08 08 08 08 08 08 08 08 04 04 04 04 02 02 01 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64
| RelativeGrowth [8/8] |
Let t2 = 1 + 2 + 4 + 8 + 16 + ... + N
Let p1 = 0 + 1 + 2 + 3 + 4 + ... + N
N t2 p1
---------------------------------------------
1 1 1
2 3 3
4 7 10
8 15 36
16 31 136
32 63 528
64 127 2_080
128 255 8_256
256 511 32_896
512 1_023 131_328
1_024 2_047 524_800
2_048 4_095 2_098_176
4_096 8_191 8_390_656
8_192 16_383 33_558_528
16_384 32_767 134_225_920
32_768 65_535 536_887_296
65_536 131_071 2_147_516_416
131_072 262_143 8_590_000_128
262_144 524_287 34_359_869_440
524_288 1_048_575 137_439_215_616
1_048_576 2_097_151 549_756_338_176
Quadratic growth is pretty bad!
Revised: 2008/03/17 13:01