I have been hearing phrases such as nlogn,O(n), etc and more for java. I'm not quite sure what this means but I know it has something to do with time/performance. Could someone explain or post a link where I can read about.

Printable View

- 06-09-2011, 07:43 AMoaklandsbestJava Performance?
I have been hearing phrases such as nlogn,O(n), etc and more for java. I'm not quite sure what this means but I know it has something to do with time/performance. Could someone explain or post a link where I can read about.

- 06-09-2011, 07:51 AMpbrockway2
- 06-09-2011, 08:24 AMoaklandsbest
For "Orders of common functions" table on that page, how would I know which notations compare against the other in terms of speed. I have heard them before used in Sorts when talking about the speeds but don't understand it really.

- 06-09-2011, 08:36 AMpbrockway2
The table goes from fast to slow. (like it says!) But notice how it says "the slower

*growing*functions are generally listed first". That's because the O() notation is defined in terms of asymptotic behaviour; we may have f(x)=O(1) and y(x)=O(n!) but still find for some specific value of*n*that f(n)>y(n). - 06-09-2011, 08:52 AMJosAH
Note that the big-Oh notation doesn't mention anything about speed; it is defined in terms of elementary steps, e.g. one comparison is one step, one swap operation is one step etc. Consider an efficient algorithm (in terms of those steps); it runs much faster on a fast computer than on a slow computer; both computers perform the same number of steps. Big-Oh defines the number of steps given the size of a problem, e.g. the heapsort algorithm takes O(n*log(n)) steps to sort n items (which is a lot better than bubble sort which takes O(n*n) steps).

kind regards,

Jos - 06-09-2011, 12:43 PMtrksoft
Analysis of Algorithms

Donald Knuth - Wikipedia, the free encyclopedia

Knuth: Selected Papers on Analysis of Algorithms