O(n) examination of a search algorithm : binarySearch[ {1,10,20,30},  10]

Here's where we get tricky.  In a loop, I generate some random lists of varying sizes, and store how they perform.
The Timing[] function can be used to see how long something takes to run; look in the documentation for the details.

verbose = False ; (* turn off printing *) counts = {} ;       &n ... timeTaken[[1]]}] ; AppendTo[counts, {logn, loopCount}],  {logn, 1, 6} ] ;

{log(n),loopCount} = {1, 3} in 0. Second

{log(n),loopCount} = {2, 7} in 0. Second

{log(n),loopCount} = {3, 10} in 0.01 Second

{log(n),loopCount} = {4, 13} in 0.09 Second

{log(n),loopCount} = {5, 17} in 0.81 Second

{log(n),loopCount} = {6, 20} in 14.46 Second

RowBox[{ListPlot, [, RowBox[{counts, ,, RowBox[{PlotStyle, , RowBox[{PointSize, [, 0.03, ]}]}]}], ]}]

[Graphics:../HTMLFiles/index_85.gif]

⁃Graphics⁃

RowBox[{ListPlot, [, RowBox[{times, ,, RowBox[{PlotStyle, , RowBox[{PointSize, [, 0.03, ]}]}]}], ]}]

[Graphics:../HTMLFiles/index_88.gif]

⁃Graphics⁃

The points here are { log(n) , expense} , so clearly the search is O( log(n) ).
The last search - 14 seconds - is for one of 1,000,000 elements.

Note that the time taken doesn't look the same as the number of times through the loop.
This isn't too surprising, since many other factors like memory swapping can get in the way.

Since this algorithm cuts the size of the list in half each time, the number of comparisons is abount log_2 n.

Log[2, 10^6]//N        (* Find x such that 2^xis 1, 000, 000 .   The //N means "convert to a number" *)

19.9316

Created by Mathematica  (September 29, 2004)