Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
The moose likes General Computing and the fly likes Computer Science notation? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Engineering » General Computing
Bookmark "Computer Science notation?" Watch "Computer Science notation?" New topic
Author

Computer Science notation?

M Burke
Ranch Hand

Joined: Jun 25, 2004
Posts: 388
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

Joined: Oct 13, 2005
Posts: 38007
    
  22
Not sure about your N-1 bits, but they might be part of cubic complexity. Start here.
J. Kevin Robbins
Bartender

Joined: Dec 16, 2010
Posts: 829
    
  13

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
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11160
    
  16

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: 388
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
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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: 388
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
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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

Joined: Oct 02, 2003
Posts: 11160
    
  16

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: 388
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Computer Science notation?
 
Similar Threads
Java Recursion and binary tree searching questions
Big O
Syntax of Array as parameter in JDK 1.6
Help me review for exam
Big OOoooooo