Welcome! Log In Create A New Profile


Big O notation

Posted by 34435360 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Big O notation
February 25, 2006 12:08PM
guys, i need help.

i don't get big-o notation AT ALL - the few pages in the textbook mean nothing to me, and i'm stuck and frustrated.

please, please, please send me a link or something to some practical "plain english" examples of how to implement big-o notation on an algorithm!

thanks in advance..
avatar Re: Big O notation
February 25, 2006 01:07PM
This one seems to be a bit clearer. The hardest part seems to be actually finding the equation itself. Unfortunately, there are no notes on that. The Big-Oh part is easy.


Re: Big O notation
February 25, 2006 05:17PM
Hi. Here's my take on Big-O. Maybe it helps you get clarity; maybe you'll see problems with my uderstanding of this that will also help me.
- One wants to know how an algorythm is going to perform (in terms of time and space).
- The algorythm alone is to be evaluated, so environmental factors such as hardware and language must be eliminated (i.e. we can't just run code and time it with a stop watch).
- The algorythm's performance is measured according to how many operations are performed.
- Formulate how the number of operations will grow as the problem size grows ( in the textbook Pg 14 this is called F(x)).
- One soon notices that only the most intensive opertaion really effects the Growth Rate as the problem size increases.
- The less contributing factors are removed from the equation giving a new formula for the Growth rate which only includes the major contributor.
- The original equation is Big-O of the new equation (i.e. Big-Odescribes the relationship between these to growth rate equations).

Re: Big O notation
February 26, 2006 10:20PM
I think TUT102 does a good job of explaining it. Can you point out the things that you don't understand?

Those examples clearly state why there are terms deemed "negligible".

I've already used this in some calculations. Now let's hope I got it right grinning smiley
Re: Big O notation
March 02, 2006 07:38PM
Thanks for all the feedback.

I did not yet have tutorial 102 before, and reviewing it made things a lot more clear.

Another useful aid was http://www.cs.wisc.edu/~hasti/cs367-common/notes/COMPLEXITY.html
which has a very friendly, non-technical approach.
Sorry, only registered users may post in this forum.

Click here to login