Registered: 13 years ago
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).