When the big Oh matters : A case of O(n) vs. O(log n)

In algorithms classes we are thought to quantify algorithms based on big Oh values. But in practice we rarely write new algorithms and analyze them.

Recently, I was reading kernel source code and found a interesting algorithm.

The task here is to find the value of iterations a loop can execute in a jiffie. Provided that the total number of jiffies is available as a global variable, we can calculate it in the following manner.

As a new jiffie starts (lets say it t) enter a busy waiting loop of i iterations.
After the loop ends check whether we have passed the jiffie t.
If not do same with a increment until we pass the current jiffie.

The value of i when we out last jiffie t is the value we need. But if linux does so it will take a long time too boot. (This is a O(n) algorithm). The basic idea for improving this algorithm comes from binary search. If the value we are searching for is between 0 and 2^32 assume it is 2^31 (middle number) and test. From the test we know whether it is smaller than 2^31 or greater than it. Know we have a smaller range, and we choose the middle number of it and come up with a much smaller number.

The actual implementation uses the same idea with a little twist:

1. First find the value of n where the loops_per_jiffie is between 2^(n - 1) and 2^n. This is found by starting at 4096 and each time doubling the value. If the wait outlasts the time of jiffie on n = 18 we know that the it is between 2^17 and 2^18.

2. Find the lower order bits in the significance order using the same method. First assume each bit is 1. If the wait outlast a jiffie it should be 0. Likewise guess all the rest values.

I think this is a good example why computer science knowledge is important for programmers.