Taking apart a sum

conwy

New member
Joined
Jul 20, 2019
Messages
14
Hi everyone,

Firstly, thanks very much for providing this forum. I'm grateful for any help & advice you can offer.

I'm reading a book called Algorithms in a Nutshell and I've come across a sum formula that I'm struggling to understand:

To understand the performance of Sequential Search, we must know how many elements it examines “on average.” Since v is known to be in the list and each element is equally likely to be v, the average number of examined elements, E(n), is the sum of the number of elements examined for each of the n values divided by n. Mathematically:

12977

From reading the surrounding material, I think I roughly get what he's trying to express, but it's frustrating to look at the formula a hundred different ways and still not be able to understand it.

What I do understand: from reading Wikipedia I think I get that the large sigma means "sum", the letter above, n, is a variable that represents some kind of "to" value, as in, "from 1 to n", the i represents the "to" value, as in "from 1 to n". As I am a programmer, this kind of looks like a for-loop, where you declare a variable, give it an initial value, the increment it until it reaches an end value, then stop incrementing.

Here are my questions:

A. What does it mean to put a fraction like 1/n immediately before a sum? From my very limited knowledge of math, I assume that when you put two values together without an operator between them, it means multiply. But how on earth does one "multiply" a fraction by a sum? Or is it the result of the sum that's multiplied here? So then if n is 3, then it's the sum of 1 + 2 + 3, which is 6. So are we multiplying 1/n by 6?

B. Now I see i placed after the sum. Again, is that a multiply? Are we multiplying everything to the left of n by n? If not, then how do you distinguish between two values next to eachother meaning multiplication vs. meaning something else? Is it some kind of contextual thing? Or are there definite rules for when something is a multiplication and when it's not?

C. Again, is this multiplication, placing n next to (n + 1)?

D. I understand what 1/2 n means, I think. It means n divided by two, right? Because you're multiplying half (0.5) by the number, which is the same as dividing it by 2. But what on earth does 1/2 on its own mean? Half of what? Is there a general rule in maths for dealing with halves on their own? Am I missing some basic obvious rule?

Since I'm struggling with this simple sum / average operation over a set, I'm guessing my math skills are pretty terrible right now. Can anyone recommend an approach to improving as soon as possible? Are there any mental tricks or tactics to improve my learning speed? Or is it, like learning Chinese, simply a matter of having seen thousands of formulas and tried to solve thousands of math problems until eventually you know them all off by heart? I figure I must be missing a lot of rules and also perhaps my mind isn't disciplined enough to really think hard and solve problems.

I'm thinking of completing basic math courses in Khan Academy, to try and get better. However, looking at the sheer number and depth of the courses, and the fact that I've just spent a solid 1-2 hours trying to grasp a simple sum operation, I'm feeling pretty hopeless. Right now it feels like I could quit my day job and spent 20 years trying to get better at math full-time and at the end of it maybe I'd be as good as a high school graduate in the year 2019. Does anyone have any words of hope or comfort?

If you don't have time to answer the questions, I totally understand, but perhaps you can point me to the general areas of math that I really need to improve on, to get good at solving something like this. Or maybe a good book. Or maybe you think Khan Academy will do the job, if I just work hard and focus for a few years?

Very keen to get your thoughts.

Many thanks ahead of time for any words of advice you can offer!
 
A is a multiplication. It means to multiply the fraction 1/2 by the result of the sum -- multiplication always requires a number (or something equivalent).

B is part of the sigma notation; the sigma means "sum of ...", and whatever follows is what you are summing. Here, you are summing the values of i, such as 1+2+3 as you suggest.

C is a multiplication -- that's just ordinary algebra. Two things next to one another are multiplied unless there is some other notation (summation, function, ...) that takes its place.

D is a fraction, which is just a kind of number. For example, 1/2 + 1/2 = 1. That's just arithmetic, and means the same thing as 0.5 + 0.5 = 1.

It appears that you would benefit from a quick review of basic algebra, if only to refresh your familiarity with the notation, so you won't be second-guessing everything.

You should probably also read up on more details of summation. You're right that it amounts to a "for loop". Sources like these might help, to start:
I'd expect a programmer to have had the necessary math (perhaps a basic course in discrete math, for example, or "math for programmers"); that would be why your book assumes this knowledge. If you didn't, then such a course (on your own, or not) could be appropriate; you'd first want to check its prerequisites, or look through it to see whether you need to review more basic material before jumping in.
 
A. Multiplying by 1/n is the same as dividing by n: 1/n * X = X/n. It appears you understand this based on what you wrote in D.
As you quoted, "E(n), is the sum of the number of elements examined for each of the n values divided by n" - we need to divide the sum by n.

B. The i after the sum is what we are adding. Initial value is 1, final is n. So it's 1/n*(1 + 2 + ... + n). And since 1+2+...+n = n(n+1)/2 (this is a well known formula), we get the result in question.

C. n(n+1) is n multiplied by (n+1).

D. So you know what (1/2)*n means, but you don't know what 1/2 means? How is it possible? When you share a pizza with a friend you get 1/2 of a pizza each. 1/2 is the number half way between 0 and 1.

I don't think it will take you 20 years to get to high school graduate level. Yes, Khan Academy is a good resource. Or just google e.g. "sigma notation explanation", find a website that does a good job explaining the concept and use it for other topics.
 
Thanks very much for your responses, including confirmations of where I was on the right track. I think I'm starting to get the hang of this. I'll check out the resources you recommended. Thanks!
 
Top