A few more points:
If there were such a thing, O(0) is best. This algorithm executes in no time regardless of the number of items. Also known as "not doing it at all". In other words, the fastest code is the code that isn't there.
Another example: Some scheduler algorithms.
Code:
For t1 in threads
For t2 in threads
If t2 != t1 and t2->Priority > t1->Priority
Return t2;
Return Idle;
This looks at every thread and tries to find one with a higher priority; if there is one, it returns it. OK, it's probably not a very good scheduler, but that's not its main problem. As I hope you can see, it executes in O(n^2): if n is the number of threads, then for each thread you create, it's got to go through the list n more times. As n gets big, the time taken to run gets really big.
Code:
MaxPriority = 0
Current = Idle
For t in threads
If t->Priority > MaxPriority
MaxPriority = t->Priority
Current = t
End If
This is more useful as a scheduler. It looks for the thread with the highest priority and runs it. It executes in O(n). When you add another thread to the list, it takes a fixed amount of time extra to run.
Code:
For i = MIN_PRIORITY to MAX_PRIORITY
If Priorities[i].First != NULL
Current = Priorities[i].First
Break
End If
This algorithm is the same as the previous one -- it picks the thread with the highest priority -- but this one is O(1). The different priority levels are separated out into queues, and it's easy to find the highest-priority queue containing a thread. Finding the right queue is O(1) (it depends on the values of MIN_PRIORITY and MAX_PRIORITY, which are fixed), and grabbing the head of the selected queue is also O(1).
If you have an algorithm consisting of several operations of different orders, always take the highest order operation. The reason for this is that you should be thinking of really big numbers. For suitably low values of n, an O(1) loop containing an O(n) loop would be dominated by the O(1) loop outside -- say, if the outer loop was going from 0 to 100, the inner loop was going from 0 to n, and n=7. But that doesn't help us. If n=10000, the effect of that inner loop is going to far outweigh the outer loop. So the overall algorithm is O(n).
These couple of posts have really been about optimisation. Always remember some golden rules of optimisation:
Premature optimization is the root of all evil - Donald Knuth (said to be the best programmer in the world)
Rules of optimzation:
1. Don't
2. (for experts only) Don't -- yet - anonymousIt's better to have a correct program running slowly than an incorrect program running quickly. I can write an incorrect program and have it execute in zero time.
This is turning into "Tim Robinson's Optimisation"...