Recommend Good Resources For Learning About Recurrences?

[algoPhobic]

Hello,

In Harvard's CS50 open courseware lecture, the running time of the Bubble Sort algorithm is analyzed. The input instance being discussed, is an 8-element-long array.

At the 42:54 mark in the video lecture, the prof professes...

(n - 1) + (n - 2) + ... + 1
= n(n -1)/2
= (n[SUP]2[/SUP] - n)/2
= n[SUP]2[/SUP]/2 - n/2

Imagine my surprise when I learned that the following solution — which I would have guessed for the above equation (where n = 8)...

= (n + n + n + n + n + n + n) + (-1 + -2 + -3 + -4 + -5 + -6 + -7 + 1)

= 7n + -27

...is dead wrong.

Am I correct is guessing that the idea|rule|law behind the prof's n²/2 - n/2 solution has something to do with recurrences?

Please, can anybody advise on what I need to study in order to grok the n²/2 - n/2 solution? As in, links to learning resources? Tutorials? Recommended reading, etc?

Thanks in advance.

 

[ksdhart2]

I wouldn't say that the concept your professor is describing is related to recurrence, but rather it's a formula that comes from taking shortcuts to not have to directly sum up a large number of entries. You may or may not be familiar with sigma notation, but what it says is:

\(\displaystyle \displaystyle \sum _{k=1}^{n-1}k=\frac{n(n-1)}{2}\)

In case you're not familiar with this notation, what it means is that we take some variable (in this case k) and let it start at a value (in this case k=1) and increment it one at a time until it reaches a target value (in this case k=n-1), and each time we'll add the value k (being the argument to the right of the "sigma" symbol. We could also sum more complicated expressions, like k², or (k-7)⁶) to a running total. So the sum written above becomes:

\(\displaystyle 1+2+...+(n-2)+(n-1)\)

You can certainly see why you'd want to have a shortcut for very large values of n. Could you imagine summing up 100 or 1000 terms, by hand? That being said, your approach does exactly that and it does work, you just made one simple error. For the case where n=8, the full sum is:

\(\displaystyle 1+2+3+4+5+6+7+8=28\), or to write that symbolically \(\displaystyle (n-1)+(n-2)+(n-3)+(n-4)+(n-5)+(n-6)+(n-7)\)

Where you went wrong is that you summed up all the way to the n-7 term, and then added an additional 1. But that gives the wrong answer, because the n-7 term is itself already the 1 at the end of the sequence. Keeping this in mind, if you rearrange the terms like you did, you'll get the right answer:

\(\displaystyle (n+n+n+n+n+n+n)-(1+2+3+4+5+6+7)=7n-28=56-28=28\)

Now, one way of deriving the shortcut formula, which your professor's video doesn't seem to have touched on, is attributed to the famous mathematician Carl Gauss. The story goes that Gauss' teacher when he was a schoolboy gave the class an exercise to sum up the numbers from 1 to 100, thinking that would keep them busy for a while. Gauss worked with it and immediately arrived at the correct answer of 5050, astounding his teacher. How he did it was to group the numbers:

\(\displaystyle 1+2+3+...+99+100=1+100+2+99+3+98+...+50+51\)

By doing this, he discovered that the first and last number (1+100) summed to 101. The second number and the second-to-last number (2+99) also summed to 101, as did the third number and the third-to-last number (3+98), and so on. Thus, he deduced that the full sum would have 50 copies of 101, and the sum would then be 5050.

In symbolic terms, we can see that the first number will always be (n-(n-1)), and the last number will always be n. Thus each pair of numbers must sum to n+1, and we have n pairs. This then gives rise to the formula, a variant of which was shown above:

\(\displaystyle \displaystyle \sum _{k=1}^{n}k=\frac{n(n+1)}{2}\)

 

[algoPhobic]

...You may or may not be familiar with sigma notation, but what it says is:

\(\displaystyle \displaystyle \sum _{k=1}^{n-1}k=\frac{n(n-1)}{2}\)
...
Now, one way of deriving the shortcut formula, which your professor's video doesn't seem to have touched on, is attributed to the famous mathematician Carl Gauss. The story goes that Gauss' teacher when he was a schoolboy gave the class an exercise to sum up the numbers from 1 to 100, thinking that would keep them busy for a while. Gauss worked with it and immediately arrived at the correct answer of 5050, astounding his teacher. How he did it was to group the numbers:

\(\displaystyle 1+2+3+...+99+100=1+100+2+99+3+98+...+50+51\)
...
In symbolic terms, we can see that the first number will always be (n-(n-1)), and the last number will always be n. Thus each pair of numbers must sum to n+1, and we have n pairs. This then gives rise to the formula, a variant of which was shown above:

\(\displaystyle \displaystyle \sum _{k=1}^{n}k=\frac{n(n+1)}{2}\)

You're AWESOME ksdhart2! Thanks!

For the first time since 5th grade, I'm feeling exhilirated again at re-learning awesome mathematical stuff! I can't tell you how sincerely grateful I am, ksdhart2! Thanks again.

You're dead right ksdhart2, about how plugging in actual numbers into formulas makes stuff really click much more concretely. I understand now how the prof arrived at his final n²/2 - n/2 function.

There's just a couple questions outstanding that would help me really nail this...

1. What does the last "+ 1" term at the end of the top-most line of this screenshot, represent? (when n = 8)
2. Why does the professor say — at around the 42:20 mark — "...Now, you might recall from high school...math or physics text books had a little cheat sheet for what these kinds of recurrences or formulas add up to. Does anyone recall?..."

I've googled around and discovered one pretty good page on Summations & Sigma Notation

Sincere thanks, again!

 

[ksdhart2]

There's just a couple questions outstanding that would help me really nail this...

1. What does the last "+ 1" term at the end of the top-most line of this screenshot, represent? (when n = 8)
2. Why does the professor say — at around the 42:20 mark — "...Now, you might recall from high school...math or physics text books had a little cheat sheet for what these kinds of recurrences or formulas add up to. Does anyone recall?..."

It seems your post got lost in the shuffle for a bit, so I apologize for not seeing it sooner. The reason the sequence ends at one is to tell you to stop summing when you reach 1. Without a clearly defined final term, the instructions would be assumed to be to keep summing forever. When n = 8, you would have:

\(\displaystyle (n-1)+(n-2)+(n-3)+(n-4)+(n-5)+(n-6)+(n-7)+(n-8)+(n-9)+(n-10)+...=7+6+5+4+3+2+1+0-1-2-...\)

As for why your professor says its a recurrence, that's just a difference in terminology. In my original post, I merely gave my opinion, not an established fact. I don't think of sums as being recurrences because I didn't learn them in that way, although I see how it could be interpreted as such. At the end of the day, it's far more important to make sure you understand the concept rather than what it's called - you can always fairly quickly adapt to calling it something different, so long as you really understand what you're doing. Hope that helps.

 

[algoPhobic]

...

\(\displaystyle (n-1)+(n-2)+(n-3)+(n-4)+(n-5)+(n-6)+(n-7)+(n-8)+(n-9)+(n-10)+...=7+6+5+4+3+2+1+0-1-2-...\)

...

Thanks again,ksdhart2. Got it. I think.

The way I'm now reading it in my own head is, "Successively decrement (n minus the next lower number) until you reach the point that (n minus the next lower number) equals 1"

Incidentally, I stumbled across this really neat use of Wolfram Alpha. Because I am more of a visual learner, visual aids like Wolfram Alpha help gently ease me into this new-found (for me) concept...

 

[ksdhart2]

The way I'm now reading it in my own head is, "Successively decrement (n minus the next lower number) until you reach the point that (n minus the next lower number) equals 1"

Incidentally, I stumbled across this really neat use of Wolfram Alpha. Because I am more of a visual learner, visual aids like Wolfram Alpha help gently ease me into this new-found (for me) concept...

That's pretty much the idea, yes. It's traditional to start at the lowest value and work your way up, but because addition is commutative, there's no reason you have to do it that way. As the example from Gauss shows, it may even be beneficial to arrange the terms in some other order altogether, if doing so allows you to cancel terms or combine terms into something more manageable. As an example of when terms might cancel out, consider this expression:

\(\displaystyle \displaystyle \sum _{k=-3}^3\:k^3=(-3)^3+(-2)^3+(-1)^3+0^3+1^3+2^3+3^3=(-3)^3+3^3+(-2)^3+2^3+(-1)^3+1^3+0^3=0\)

Here, by arranging the terms in a different way, we can esee that each pair of terms sums to 0, with the lone 0³ left over, which is also equal to 0. So the sum is thus 0.

And I definitely agree with WolframAlpha is very useful. It can do many, many things. I'm actually considering buying a subscription to the Pro version.

 

[algoPhobic]

...
\(\displaystyle \displaystyle \sum _{k=-3}^3\:k^3=(-3)^3+(-2)^3+(-1)^3+0^3+1^3+2^3+3^3=(-3)^3+3^3+(-2)^3+2^3+(-1)^3+1^3+0^3=0\)
...

Thanks ksdhart2. You're very good at expanding out the summation's closed-form there. That's a new term I learned that the other day from one of my computer science algorithm books ;¬)

Speaking of which. When I tried to do what you did, and expand out that \(\displaystyle \displaystyle n log n\) summation — which evidently describes the nested for-loop that is used a lot in programming — it threw me for a loop...

int sum = 0;

int n = 8; /* or some other power of 2 */

for( int i = 1; i <= n; i*=2 ){ 
    for(int j = 1; j < = n; j++ ) {
          sum++;
    }
}

I tried expanding out the closed-form of the book's \(\displaystyle n log n\) summation but the best I could do was work out that for n = 8, the sum evaluates to 8 + (8 * 3) (i.e. 32).

Please can you show me your magic, kdshart2, by expanding out the summation for \(\displaystyle \displaystyle n log n\) like you did for your \(\displaystyle \displaystyle \sum _{k=-3}^3\:k^3=...\)? For n = 8, for example?

Do you know how to make Wolfram Alpha do that kind of exploded expansion? Or is that feature only available in the Pro version?


Thanks in advance.

 

[ksdhart2]

Hrm... interesting. I'm not really sure what to make of the n log(n) summation. Various sources, including WolframAlpha confirm it's true, but I'm not sure I fully understand it. I'm assuming that log(n) is to be interpreted as the natural logarithm (i.e. base e). Sigma notation only works if the upper and lower bounds of the index variable are integers. To the best of my knowledge, summations with non-integer bounds are undefined. So, I think that means that the sum is only valid if log(n) is an integer, which means that n must be an integer power of e. But the sum appears to be defined and work for any real number n, which to me implies that there's something more here I'm not seeing.

 

[algoPhobic]

Hrm... interesting. I'm not really sure what to make of the n log(n) summation. Various sources, including WolframAlpha confirm it's true, but I'm not sure I fully understand it. I'm assuming that log(n) is to be interpreted as the natural logarithm (i.e. base e). Sigma notation only works if the upper and lower bounds of the index variable are integers. To the best of my knowledge, summations with non-integer bounds are undefined. So, I think that means that the sum is only valid if log(n) is an integer, which means that n must be an integer power of e. But the sum appears to be defined and work for any real number n, which to me implies that there's something more here I'm not seeing.

Whenever anybody uses log \(\displaystyle \displaystyle n\) in the context of computer science, it means log₂ \(\displaystyle \displaystyle n\) — not log_e \(\displaystyle \displaystyle n\). So \(\displaystyle \displaystyle n\) in this case is assumed to be a power of 2. Hence my original request to let \(\displaystyle \displaystyle n = 8\) — plus the comment in the for loop code I posted earlier.

So, when \(\displaystyle \displaystyle n = 8\), the upper bound of the index would be 3 (log₂ 8) — meeting the Sigma notation's integer constraint.

Having said that, it is also common practice in the world of algorithm analysis, that the base of the logarithm doesn't really matter whenever you're analyzing any "function" (read: "algebraic expression"). The reason being, it is always possible to convert from one base to another.

If you're curious to get a clearer understanding of the back-story behind my question, the book I referred to earlier can be downloaded here (see pages 31 and 70).

Oh well. Yet another one of the many formulas that I will never fully understand, and just have to commit to rote memory and accept it on faith that it's correct :¬)

Thanks just the same, for trying in any case, ksdhart2.

 

[ksdhart2]

That's an interesting notational convention. I can't say as though I've ever encountered such a convention before in any of my programming classes. I was having a discussion a while back with another member of this forum about how communicating math can be difficult and confusing at times because different people may mean different things by the same notation. When I was learning math in school, the standard was that log(x) meant the base-10 logarithm, and ln(x) was the natural log. But then when I was learning programming, the standards there were to have log(x) mean the natural logarithm and you'd have to specify if it was meant to be base-10. Once I did a bit of digging, I found that it makes sense, because the programming languages are programmed such that the Math.log(x) function returns the natural logarithm. That said, I can definitely see the logic behind interpreting log(x) as the base-2 logarithm. A binary logarithm could be useful in many aspects of computer programming. It's another case of where the way you learned it isn't "wrong," it's just not what I'm used to seeing is all.

I do understand how the summation works for cases where log(n) is an integer. I just don't know if it holds for all real numbers, and if it does how/why. In the case of n=8, the expansion of the sum is:

\(\displaystyle \displaystyle \sum _{k=1}^{log_2\left(8\right)}\:8=\sum _{k=1}^3\:8=8+8+8=8 \cdot 3=8 \cdot log_2(8)=24\)

Incidentally, you can use another of the common closed-form expressions for sums to see the same thing:

\(\displaystyle \displaystyle \sum _{k=1}^n\:C=C \cdot \sum _{k=1}^n\:1=C \cdot n\)

Here, C and n are any arbitrary constants. Using that formula , we then have:

\(\displaystyle \displaystyle \sum _{k=1}^3\:8=8 \cdot \sum _{k=1}^3\:1=8 \cdot 3=24\)

 

[algoPhobic]

...

But then when I was learning programming, the standards there were to have log(x) mean the natural logarithm and you'd have to specify if it was meant to be base-10. Once I did a bit of digging, I found that it makes sense, because the programming languages are programmed such that the Math.log(x) function returns the natural logarithm...
...
I do understand how the summation works for cases where log(n) is an integer. I just don't know if it holds for all real numbers, and if it does how/why. In the case of n=8, the expansion of the sum is:

\(\displaystyle \displaystyle \sum _{k=1}^{log_2\left(8\right)}\:8=\sum _{k=1}^3\:8=8+8+8=8 \cdot 3=8 \cdot log_2(8)=24\)
...
\(\displaystyle \displaystyle \sum _{k=1}^3\:8=8 \cdot \sum _{k=1}^3\:1=8 \cdot 3=24\)

You RAWK, kdshart2! Thanks for that man! It looks like I was kinda close with my earlier \(\displaystyle \displaystyle 8 + (8 * 3)\) attempt :¬)


I was just reading somewhere the other day (if i find it later, I'll post it) that the reason computer science algorithm analysis uses log₂, is not because of of any particular programming language implementation detail. Rather, the convention of using log₂ has something to do with the concept of what's called "A Turing Machine" — evidently. But I suspect, we're probably saying the same thing. Just different words.


The book I referred to earlier talks about \(\displaystyle \displaystyle \sum _{k=1}^{log_2\left(n\right)}\:n= n{log_2\left(n\right)}\) in context of the code that I posted earlier (see Example 3.12 on page 70)...

int sum = 0;

int n = 8; /* or some other power of 2 */

for( int i = 1; i <= n; i*=2 ){ 
    for(int j = 1; j < = n; j++ ) {
          sum++;
    }
}

For what it's worth, plugging 8 into \(\displaystyle \displaystyle n\), and running the code, \(\displaystyle \displaystyle sum\) ends up being 32. But your Sigma notation expansion makes it 24. Can you help me understand why the books code summation and your Sigma notation summation don't jibe, please ksdhart2?

Thanks again.

 

[ksdhart2]

Ah, okay. I see what's going on the with the code. It's one of the most common errors I see, and it even often plagues me. We often call it "fencepost error" or "off-by-one error." The outer loop of your code is meant to count up, in powers of 2, until it reaches the given n. The inner loop counts from 1 to n. The inner loop does what you want it to do, but its the outer loop that runs one too many times. If we step through just the outer loop, maybe you can see what's going on and how to fix it.

for (int i = 1; i <= n; i *= 2)
{
   cout << i << " ";
}

All that code does is run the outer loop and print the value stored in i to the screen. It prints:

1 2 4 8

You can see that your code will run the inner loop, even when i is equal to 8 (n), for a total of four times. But that's not the behavior you want - you want it to stop running at that point and only run the inner loop three times. Can you see why that happens?

 

[algoPhobic]

...
its the outer loop that runs one too many times. If we step through just the outer loop, maybe you can see what's going on and how to fix it.

for (int i = 1; i <= n; i *= 2)
{
   cout << i << " ";
}

All that code does is run the outer loop and print the value stored in i to the screen. It prints:

1 2 4 8

...
...that's not the behavior you want - you want it to stop running at that point and only run the inner loop three times...

That's very generous of you and all, kdshart2. But with all due respect, I'm not after a code review here :¬)

It's not my code after all. So I can't say that I want it do behave in any particular way. Besides. Whether the author has published good code or bad code for his examples, I think it's fair to say that's a discussion for another forum :¬)

What I am after is an understanding of how the algebra summations in that book, jibe with the code from that book — which refers to those summations.

The book says the outer loop runs log₂ n + 1 times. So since log₂ 8 = 3, that makes 3 + 1 = 4. So according to the author of the book, the outer loop is doing exactly what the author describes.

The book then goes on to say, "...the inner loop always executes n times...". Again, when n = 8, that'll get you 8 * 4 which I'm pretty confident equals 32.

See what I mean here?...

​

 

[algoPhobic]

If anybody's interested, here's that Turing Machine discussion I referred to earlier...

 

[ksdhart2]

Oh! I misunderstood what you were asking. I'm sorry. I thought you had written that code yourself and were wondering why it returned a different answer than you were expecting. Best as I can tell, the disconnect between the sum and the code is that the code's not actually doing the same thing as the sum. The comment on the code from Example 3.13 from your book indicates the outer loop runs "log(n) times" but as you've identified (and it even says later in the paragraph) it actually runs log(n)+1 times. The inner loop runs n times and all it does is increment a variable by one. Accordingly, you have an outer loop that runs log(n)+1 times that ends up incrementing a variable by n (via the inner loop running n times). That calculation is, of course, going to return \(\displaystyle n \cdot (log(n)+1)\), not \(\displaystyle n \cdot log(n)\).

 

[algoPhobic]

...I misunderstood what you were asking...I thought you...were wondering why it returned a different answer than you were expecting...

No problemo, mi amigo! Prolly another case of "same meaning — different words", I'm sure...

...
...The book I referred to earlier talks about \(\displaystyle \displaystyle \sum _{k=1}^{log_2\left(n\right)}\:n= n{log_2\left(n\right)}\) in context of the code that I posted earlier (see Example 3.12 on page 70)...
...
...the book I referred to earlier can be downloaded here (see pages 31 and 70)...
...
...Please can you show me your magic, kdshart2, by expanding out the summation...?
...
...Can you help me understand why the books code summation and your Sigma notation summation don't jibe, please ksdhart2?...
...

Since it looks like none of that hit home until I finally posted the screenshot of the book, from now on I won't confuse the issue by trying to explain with words. Instead I'll just cut to the chase with screenshots of whatever I'm asking about. Would that help?

Either way. You still RAWK in my book regardless, ksdhart2 ;¬)

 

[Steven G]

Hello,

In Harvard's CS50 open courseware lecture, the running time of the Bubble Sort algorithm is analyzed. The input instance being discussed, is an 8-element-long array.

At the 42:54 mark in the video lecture, the prof professes...

(n - 1) + (n - 2) + ... + 1
= n(n -1)/2
= (n[SUP]2[/SUP] - n)/2
= n[SUP]2[/SUP]/2 - n/2

Imagine my surprise when I learned that the following solution — which I would have guessed for the above equation (where n = 8)...

= (n + n + n + n + n + n + n) + (-1 + -2 + -3 + -4 + -5 + -6 + -7 + 1)

= 7n + -27

...is dead wrong.

Am I correct is guessing that the idea|rule|law behind the prof's n²/2 - n/2 solution has something to do with recurrences?

Please, can anybody advise on what I need to study in order to grok the n²/2 - n/2 solution? As in, links to learning resources? Tutorials? Recommended reading, etc?

Thanks in advance.

Here is a variation of ksdhart2's method.

Let S = 1 + 2 + 3 + ... + (n-1) + n
Also S= n+(n-1)+(n-2) + ... + 2+1

Adding the two equations gives us 2S= n(n+1) and therefore S= n(n+1)/2

 

[algoPhobic]

Here is a variation of ksdhart2's method.

Let S = 1 + 2 + 3 + ... + (n-1) + n
Also S= n+(n-1)+(n-2) + ... + 2+1

Adding the two equations gives us 2S= n(n+1) and therefore S= n(n+1)/2

Thanks for that, Jomo.

For what it's worth, the summation calculated by the book's code, jibes correctly with the manual summation of the book's \(\displaystyle \sum_{i=1}^{n} i = \frac{n(n+1)}{2}\) closed-form equation...

 

[algoPhobic]

He Blinded Me With Science!

I happened to stumble on an awesome video that explained your summation variation for me very clearly, Jomo.

That same video — where the teacher starts talking about "The Summation Of A Constant", also helped me to finally understand the summation equation I've been puzzling over (@6:24)...

​

After rereading page 71 of the book three or four (OK seven :¬)) times, I eventually focused in on something that I'd been ignoring all along because I thought it was only a typo: \(\displaystyle \displaystyle \sum_{i=0}^{\log n} n\).

That equation in the first paragraph of page 71, looks only ever-so-subtly different from the other equation that I'd been fixated on; the one the author refers to as "Equation 2.3": \(\displaystyle \displaystyle \sum_{i=1}^{\log n} n\). Can you spot the difference?

So I punched \(\displaystyle \displaystyle \sum_{i=0}^{\log n} n\) into Wolfrom-Alpha to compare the pg 71 equation result to the "Equation 2.3" result. And I discover this little beauty: \(\displaystyle \displaystyle \sum_{i=0}^{\log n} n = n(\log n + 1)\).

I connected the dots from the closed-form part of that — \(\displaystyle \displaystyle n(\log n + 1)\) — to the book's — "The first code fragment has its outer for loop executed log n + 1 times..." — clue on page 71.

My new-found discovery of the concept of "The Summation Of A Constant", brought it all together for me. So finally, I understand how to expand out the equation to make the solution jibe with the programmatic summation in the book's Example 3.13 for loop...


let n = 8

\(\displaystyle \log_2 8 = 3\)

\(\displaystyle = n(\log n + 1)\)

\(\displaystyle = 8(3 + 1)\)

\(\displaystyle = 8(4)\)

\(\displaystyle = 32\)


The thing that had me spinning my wheels, was not fully understanding what the book was trying to tell me all along — "...the total cost for the first code fragment can be expressed as \(\displaystyle \displaystyle \sum_{i=0}^{\log n} n\)...".

Instead, I was fixated too intensely on this part — "...From Equation 2.3, the solution for this summation is \(\displaystyle \Theta(n log n)\)...".

The theory I'm working under at this point of my understanding, is that the author's intention was to say that \(\displaystyle \displaystyle \sum_{i=0}^{\log n} n\) represents the actual summation of the for loop, but that "Equation 2.3" is only an indirect shortcut between the actual summation, and the final \(\displaystyle \Theta(n log n)\) running time solution.

Jeesh! I wish these computer book dweebs would just say what they freakin' mean for once! LOL!

Seriously though. The moral of this story? If you're still in grade school or high school, not only make sure you learn as much algebra as you can — while you can. But also make doubly sure you don't forget it after you finish high school. You most definitely will regret it if you let it get rusty, like I did.

Thanks again to kdshart2 and Jomo for yall's input :thumbsup: