"tshad" <ts**********@f tsolutions.comw rote in message

news:eF******** ******@TK2MSFTN GP03.phx.gbl...

What does O(n) and O(lg(n)) mean?

It's a Computer Science way of describing the complexity or cost of an

algorithm. The "n" relates to the size of the data, the "O" is read "order"

and the actual function describes how the length of the operation varies

according to the length of the data given the operation.

In this particular case, O(n) refers to the fact that a straight linear

search through the data will always take an amount of time that is directly

proportional to the size of the data, and increases linearly as the size of

the data increases. On the other hand, the BinarySearch method takes

advantage of the fact that the data is sorted, allowing a search for a

particular data item to increase in time proportional to log(n). Since

log(n) is always much smaller than n itself, this means BinarySearch is much

more efficient, on average.

If you intend to do any serious programming, especially where performance is

an issue, you would do well to find a good textbook or other reference on

algorithms and learn not only about the concept of "order", but also what

common algorithms have what order and how the order is affected by the data

(for example, the average case for a binary search is O(log(n)), but

depending on how the data is stored the worst case might wind up being O(n)

anyway).

Pete