Archived

This topic is now archived and is closed to further replies.

sofsenint

Big-O Notation

Recommended Posts

I''ve been preparing for the APCS AB exam next Wednesday. I''ve heard that there''s a lot of questions about Big-O notation on it and have been having a littlte bit of trouble with it. Does anyone know of a good online lesson over it? ----------------------------- Weeks of programming can save you hours of planning. There are onle 10 kinds of people in this world-- those who understand binary and those who don''t.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Go look in your pre-cal or calculus book about end behavior. Also look into a section about comparing growth rates of functions as they tend to infinity.

Share this post


Link to post
Share on other sites
It''s funny you ask necause I seem to have been taking a previous year''s exam and run across a question about it, but had never heard of it let alone know what they were talking about...

I Also would like to have some info on what it is... Thanx a lot!

Dwiel

Share this post


Link to post
Share on other sites
Thanks a lot for your help! Sorry that I didn't search on Google first, I should have thought of that.

BTW (to Tazzel3D)- Big O notation is a method of classifying algorithms by how efficient their run-times are. You typically use the number of items the algorithm is acting on as n. So, an algorithm that looks at all n items, or some part of n directly proportional to the number of items would be O(n). An algorithm that wasn't at all affected by the number of items in n would be O(1). Something like a binary search would be O(log n), while an insertion sort would be O(n^2). The article Burning_Ice gave can explain it better than I can.

[edited by - sofsenint on May 1, 2003 10:51:48 PM]

Share this post


Link to post
Share on other sites