programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

Computer Science notation?

M Burke
Ranch Hand
Posts: 410
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?

Campbell Ritchie
Sheriff
Posts: 55351
157
Not sure about your N-1 bits, but they might be part of cubic complexity. Start here.

J. Kevin Robbins
Bartender
Posts: 1801
28

fred rosenberger
lowercase baba
Bartender
Posts: 12529
48
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".

M Burke
Ranch Hand
Posts: 410
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?

Paul Clapham
Sheriff
Posts: 22379
42
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: 410
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?

Paul Clapham
Sheriff
Posts: 22379
42
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.

fred rosenberger
lowercase baba
Bartender
Posts: 12529
48
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: 410
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.