i should add that i have read the appendix on O-notation now...
some of it makes sense, some of it does not.
i need english terms!!
is it correct that if i say something will run in O(N)
then it must run once for each N (pointer in the tree)
and if it will run (2N) then it must run twice for each N (pointer in the tree)??
Correct, but no one says O(2N), as that is still O(N). The idea
of Big-O is that we can ignore constant factors. O(N) and O(17N
+ 42) are the same. The second half of the lecture on Debugging
is an hour about Big-O in the context of the Game of Life. You
may find it easier to wath that than the read the note below.
If someone says "I'll walk over: I'll be there in 5 minutes"
you cut them some slack, and expect them in the next quarter
hour. If someone says "I'll call next week", you don't
hold them to 7 days. You have an informal sense of time that
distinguishes 15 minutes from 15 days. Big-O is a
formalization of that sense.
If you have an algorithm for problem 13 on the midterm which
walks the list once to get the length, a second time to find the
midpoint, and a third time to get the end of one of the lists to loop
it up, you have done something N + N/2 plus N/2 times, or 2N
operations. This is still O(N).
If you think about problem 11, which reversed the list with N
steps of average length N/2, you are doing N^2/2 operations. The
key insight here is that growing with N is much easier to deal with
than growing with N^2.
Let's talk about the Methodists. The best seller
"Tipping Point", discusses their theory of growth.
They noticed that as a group grows, the number of possible
relationships grows much faster. The Methodists decided
that rather than deal with congregations so large that all the members
would not know each other, they would split a congregations when it
hit 150 members. What is the problem they are solving?
If you are at a table with 5 people, and you declare a toast, and
everyone clinks glasses with everyone else, you will find that 5 of
you clink with 4 others. We are counting the clinks twice: there
are only 5 x 4 / 2, or 10 clinks. If you have 100 people
at a party, and you need to clink with 99 others, for a total of
4950 clinks (100 * 99 / 2). As the party gets bigger, the
number of interactions increases as the square of the members
present. The fact that it is N*(N-1)/2 rather than N^2 is much
less important than the fact that it is quadratic. That is, N *
(N-1) is almost the same thing as N*N. The difference between
10000 and 9900 is much smaller than the difference between 100 and
10000. The difference between N^2/2 and N^2 is also not so
important as the difference between N and N^2. It turns out that
more than 150 * 149/2 interactions is too complex for most humans
("I can't invite Bill and Jim to the same prayer meeting, as they
as still fighting about what Sue told Jane.") Less than
150, and most people can keep the relationships in pretty fair
order.
The fact that we can ignore constants allows you to perform many
Big-O operations in your head. (Hmm. One count, O(N).
One traverse half way to split. O(N). One final
traverse to link the last element in: O(N) for a total of O(N).)
Given a set of N items, if you need to compare each item to the
others, you have N^2 operations to deal with. If you can
organize things so that you only have to look at some representatives,
you may be able to do the task in much less time.
- jeff parker
