M Burke

Ranch Hand

Posts: 406

posted 4 years ago

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?

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?

Campbell Ritchie

Sheriff

Posts: 53743

127

posted 4 years ago

Not sure about your N-1 bits, but they might be part of cubic complexity. Start here.

posted 4 years ago

Try this page.

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." -- Ted Nelson

posted 4 years ago

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".

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

Posts: 406

posted 4 years ago

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?

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?

posted 4 years ago

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 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

Posts: 406

posted 4 years ago

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?

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?

posted 4 years ago

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:

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.

`. 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 * * * * * -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.

posted 4 years ago

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.

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

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

Posts: 406