Preserved Topic: Big O Notation (Page 1 of 1)

I'm taking Comp Sci III and I've finally come to the conclusion that I can't avoid needing to know Big O Notation. Anyway, I've found plenty of websites explaining algorithm analysis, but I want some example problems to practice working out.

My textbook doesn't provide much, and I found this... http://www.cs.utk.edu/~booth/311-01/notes/aaproblems.html
which helps, but I'd REALLY like a little bit more... Anybody know of any sites offhand where I can find functions and solutions? Keeping my toes crossed and muttering "Please don't make me know that, please don't make me know that" isn't helping anymore.

Thanks!

Big O Notation

Does that help at all?

Jestah

Hehe, I saw that one earlier, it's not really what I needed, but thanks! )

why must everything be sooo boooring?!

Lovedove - Can you be more specific in what you're looking for?

Genis - The members of the Asylum have been very clear in not wanting you around. Since you refuse to just leave we thought we'd try to bore you away. It doesn't seem to be working, your still around.

Jestah

genis: I for one would like to say that I appologize that we can't keep all the topics to your liking. maybe we can just ask you before we post a thread if it is to your liking or not.

maybe we could start a topic on "The things genis doesn't find boring" and just discuss that. How would that be?

Later,

C:\


~Binary is best~

Or - now hold one moment, this may be a really *bizzare* and hard to grasp concept - genis could simply not bother reading or posting in threads that he fins not suitable for him

I know....outlandish and complicated, but hey...it was a thought...

Sorry dove, can't help any.

good point DL. LoveDove, I would love to help you out but by the looks of the site that Jestah posted I am uterly confused. I have no idea.

Later,

C:\


~Binary is best~

DL and CPrompt, thanks anyway! )

Jestah, I just want like, a set of functions or algorithms that I can look over and figure out the O Notation for. Most of what I find are explinations, but I just need something I can use for practice... Like the type of stuff you'd find at the end of a chapter in a textbook. Thankyou for looking though ) I'll probably hit the library later and see if I can find textbooks that offer more than the one I need for my class does.



[This message has been edited by lovedove (edited 01-08-2003).]

I've still got my discrete math book from last semester. Unfortunately, I have to run off to my calc3 class for an hour first But if you like, I can post a few of the problems from that for you.

Well, if you can, dig out some of your old programs from Comp Sci I and II and analyze those using big O. You did save those, right?

Also, usually Comp Sci I and II level textbooks should have lots of program examples.

You can also practice the reverse and create sample programs/algorithms for each of the common big O notations.

Hehe silence, yes, I saved them, but the problem is ater I analyze the program, how do I know I did it correctly? Knowing me I'll start randomly making up answers and give myself 30 reasons for why they all work...

Anyway, after reading Raptor's post, I checked my old discrete book, and there is a section in there on it. I would never have thought to look there because my discrete professor never mentioned order notation... SO, thankyou Raptor ) hehe

Big O notation is no little topic many people spend their entire live analysing algorithms efficiencies. A lot of it is guess work, and a lot more of it is hard work plugging numbers.

G. Brassard and P. Bratley, Fundamentals of Algorithms, Prentice-Hall, 1996; ISBN (McGraw-Hill Edition): 0-13-335068-1

Is a book that I read on algorithms with a huge study of Algorithm efficiency analysis. It is a truely awful book, but it does go into detail about notations, since the entire book forcuses on it in an abstract way.

For most basic computer science classes you could most likely get by knowing that:

1) A single selection of an object is given in constant time 'c' which is normally denoted O(1) since constants are rounded not really looked at in examining the efficiency of an algorithm. O(c) makes no sence in big O notation, since constants are ignored. A case of this would be an oporation along the lines of "Select the 'i'th element of an array".

2) A loop is given in the time 'n', where 'n' is the number of times that the loop is executed. This would be denoted O(n). An example of this would be a for loop, "For each element of an Array where the array is of size n". If you have nested for loops you the time would be multiplicated. If you have two for loops, one inside the other.

for i <- 0 to n do

    for j <- 0 to n do

        //do something

you would have a running time of n^2 (n-squared) three nested for loops would be in the order of n^3 (n-cubed). Which would be written O(n^2) or O(n^3) respectively.

3) If you have two different loops say

for i <- 0 to n do

    for j<- 0 to m do

        //do something

you would have a bigO time of O(nm). Make sure you consult your instructor on how this should work. Many times you would want it in terms of a single variable, which is beyond the scope of what I can show you.

4) If you have two for loops one following the other you would be running in the order of a combination. Say O(n + n) or O(n+m) which in this case you would apply the Maximum rule which tells you only to use the larger value. So if n were larger than m you would have a running time of O(n).

5) While loops, if you know the terminator, can be handled much like the for loops are handled above.

6) Recursion is handled in a much different way. And is beyond the scope of anything I could attempt to type you.

The reason I tell you this is because there is so much in the way of solving for this kind of stuff that using it practically can take you so many hours, even days. Trying to solve the quick sort algorithm took me a good 12 hours.

If you are going to attempt this it is normally done in classes that do not focus on Algorithms on basic for loops. You will not get much more advanced than that.

If you still think you should look at more algorithms you might want to try. http://www.cs.sunysb.edu/~algorith

Happens to be my school and the second link on google for algorithms (was #1 last time I checked).

War, wow, thanks for the explination! *shares purple crayons with you*

Thanks, one of my favorite colors.

If you really get into it you will read all about theta and omega notations. Those are even more fun good luck with it all.

Hehe, yeah, we did omega and theta notation in a previous course... But my professor says he's not going over it again, thank goodness.

They tought you those notations first? Wow, that is a bit interesting. I would expect it to traspire in that order.

They taught Big O in CS1; Omega, Theta, little o, and 1 other in CS2; and now they are going deeper into Big O in CS3.

The way I've always thought about O notation is this:

I consider each O(1) statement (a statement that takes a constant amount of time regardless of any important outside factors) to be a square. Or a block. Something like that. Just a little white square hovering in space.

[] <- sorta like that. Only shorter.

A for loop would create a line of these squares. For instance:

for (int a=0; a < n; a++)
doSomethingOrderOne();

would be represented by:

[][][][]...[][][][] (length=n)

Since each call to doSomethingOrderOne() takes time O(1).

This is a line. Lines are one-dimensional. So the for loop is O(n) (in other words O(n^1)). Make sense?

Then, if you have two nested for loops:

for (int a=0; a < n; a++) {
for (int b=0; b < n; b++) {
doSomethingOrderOne();
}}

it's represented like this:

[][]...[][]
[][]...[][]
...............
[][]...[][]
[][]...[][] (width = n)
(height = n)

That's a two-dimensional object, so you can see that it's O(n^2), because it becomes a square of height and width n. You can take the area of that square and remove any constants from it - hence the n^2.

Then, consider this example:

for (int a=0; a < n; a++) {
for (int b=0; b < a; b++) {
doSomethingOrderOne();
}}

it's represented like this:

[]
[][]
......... (width at any point = height at that point)
[][]...[]
[][]...[][] (width = n)
(height = n)

(In this example, the squares were drawn from top to bottom, and then from left to right. The top represents a=0, the bottom a=n, the left b=0, and the right b=a.)

Notice how it forms a triangle. The area of this triangle is (1/2)n^2. Since we throw away constants, it's O(n^2). Try to see why that makes sense.

Now, this can be extended into three (or more) dimensions with your imagination. I'm just trying to give you an intuition for it. I hope that helped =)

Wow, you are too cool. I see little squares in my head now and they make sense )



[This message has been edited by lovedove (edited 01-14-2003).]