I am reading books on data structures. example They are using a notation I am not familiar with. Like; 'N(N-1)(N-2) / 6 = N^3/6 -N^2/2 + N/3' and 'Big O' and so on to describe memory usage and performance. Anyone know of a tutorial that can get me up to speed on this?

It's basically showing you the formula for computing how many iterations are needed to finish the task.

For example...

If i wanted to print out every element from a list, and the list is size N, I need to print out N elements. Simple enough.

Now suppose the list is of people, and I want to print out how many ways they can shake hands. For now, let us assume there are three people. So, each person (of which there are three) needs to shake the hands of every other person - that would be two others, making 6 handshakes. But, if A shakes B's hand, B does NOT need to shake A's hand again. So, I need to divide the result by 2, giving 3 total handshakes.

Assume there are four people. I'd have 4 people shaking 3 people's hands, and again, divide by 2.
Assume there are five people. I'd have 5 people shaking 4 people's hands, and again, divide by 2.

So...Generally speaking, if I have N people, I'd need to have (N)*(N-1) / 2 handshakes.

--------------------

Your example might be for something like picking three people out of a group of N total people.

I have N choices for the first person, N-1 choices for the second, and N-2 for the third person, giving me 'N(N-1)(N-2)'.
But since the team of fred, Campbell and JK is the same team as JK, Campbell and fred, I need to divide my total by the ways those three can be arranged, hence the "/6".

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

M Burke
Ranch Hand

Joined: Jun 25, 2004
Posts: 397

posted

0

fred rosenberger wrote:It's basically showing you the formula for computing how many iterations are needed to finish the task.

For example...

If i wanted to print out every element from a list, and the list is size N, I need to print out N elements. Simple enough.

Now suppose the list is of people, and I want to print out how many ways they can shake hands. For now, let us assume there are three people. So, each person (of which there are three) needs to shake the hands of every other person - that would be two others, making 6 handshakes. But, if A shakes B's hand, B does NOT need to shake A's hand again. So, I need to divide the result by 2, giving 3 total handshakes.

Assume there are four people. I'd have 4 people shaking 3 people's hands, and again, divide by 2.
Assume there are five people. I'd have 5 people shaking 4 people's hands, and again, divide by 2.

So...Generally speaking, if I have N people, I'd need to have (N)*(N-1) / 2 handshakes.

--------------------

Your example might be for something like picking three people out of a group of N total people.

I have N choices for the first person, N-1 choices for the second, and N-2 for the third person, giving me 'N(N-1)(N-2)'.
But since the team of fred, Campbell and JK is the same team as JK, Campbell and fred, I need to divide my total by the ways those three can be arranged, hence the "/6".

Well, I sort of follow. Each person down the line, when it's their turn to start shaking hands, don't have to shake hands with the people who already went down the line. But how does the division by 2 take that into account? The (N)*(N-1) part I think I get, it means a person can only shake hands with one person at a time, yes?

M Burke wrote:
Well, I sort of follow. Each person down the line, when it's their turn to start shaking hands, don't have to shake hands with the people who already went down the line. But how does the division by 2 take that into account? The (N)*(N-1) part I think I get, it means a person can only shake hands with one person at a time, yes?

No, it means that each person only shakes hands with every other person once. The "/2" part means that when I shake hands with you, then you are shaking hands with me at the same time.

It isn't necessarily easy to see this sort of thing by reading descriptions. Instead you should write down some small examples and see what's going on.

For example, suppose there are only two people, A and B. They shake hands and that's all. One handshake.

Now suppose there are three people -- A, B, and C. A shakes hands with B and then with C. (2 so far.) B already shook hands with A, so she shakes hands with C. (3 so far.) C has now shaken hands with the other two so that's all.

So do those numbers agree with the formula for N=2 and N=3? What about N=4?

M Burke
Ranch Hand

Joined: Jun 25, 2004
Posts: 397

posted

0

I do understand how the formula works, and I do see how the logic progresses:
So if N = 4

A shake B
A shake C
A shake D
B shake C
B shake D
C shake D

At this point, everyone has shaken everyone else's hand.

That is 6 shakes and (4)*(4-1)/2 = 6

But the logic on how to derive the equation escapes me. (A code example may also help me)
Is there a tutorial out there than explains this logic process?

It seems pointless to write a tutorial for deriving just this particular equation. In fact if such a thing existed I would call it an "explanation" rather than a "tutorial". Here's an explanation with pictures:

. A B C D E F
A - x x x x x
B * - x x x x
C * * - x x x
D * * * - x x
E * * * * - x
F * * * * * -

This one happens to be for 6 people, but that doesn't matter. It works for any n people. The grid shows possible handshakes between the participants. The "-" entries are where a participant would shake hands with herself, so we exclude those. The other entries are possibilities. But there's a symmetry in the diagram: for every pair there's a "x" where Q shakes with R and a "*" where R shakes with Q. So we only need to count the "x" entries, the "*" entries are duplicates.

Now there are n^2 entries in the grid. We eliminated the diagonal, which contains n entries, so we're left with n^2 - n. And half of those are duplicates (that symmetry) so the answer is (n^2 - n) / 2.

Paul Clapham wrote:Now there are n^2 entries in the grid. We eliminated the diagonal, which contains n entries, so we're left with n^2 - n. And half of those are duplicates (that symmetry) so the answer is (n^2 - n) / 2.

And note that (n^2 - n) can be factored. We can pull out the 'n', leaving us with n(n-1).

This sort of thing is covered in a basic discrete mathematics class. It is a subject called "combinations and permutations".

Combinations refers to how may different ways you can pick X items from a set of Y items. I.e. you have 10 people, how many ways can you choose 3. By definition, the order doesn't matter - as in our handshake example. It doesn't matter if you pick "Fred" first and then "Paul", or "Paul" first and then "Fred" - either way, the handshake counts for the two of us to have shaken hands.

Permutations are the same thing, but the order DOES matter. If i have nine baseball players, there is one way to pick a group of nine for my team. But there are a LOT of different ways I can set up my batting order - 362,880, in fact.

M Burke
Ranch Hand

Joined: Jun 25, 2004
Posts: 397

posted

0

fred rosenberger wrote:
This sort of thing is covered in a basic discrete mathematics class. It is a subject called "combinations and permutations".

There we go, now I have something I can look up and learn in a generic fashion that solves these type of problems, thanks.