Python

Search Algorithm Timing

Compare the predicted and actual run times of your sequential search, your binary search, and pythons built-in search.

You can assume pythons built-in search is linear, O(n). Create tables and graphs of your timing data and predictions. The list class index method uses pythons built in search to give the index of a certain value.

ind = my_list.index( value )

This method will crash or raise an exception if it does not find the value sought. You can handle the exception with try/except. However, there is a simpler way to time python searchs worst case behavior. Looking for a value not in the list takes n comparisons. So does looking for the biggest value in a sorted list. That value will be found and will not cause a crash. Just make a list of the values 1 through n and search for n to get worst case behavior. Do all searching on SORTED lists. Sequential and python search work on unsorted data but just use sorted data for all timing. Do all timing for all algorithms on the same computer. To get an accurate timing of something fast, remember that you can increase n (make a larger list) and/or you can do the search k times, then divide the time by k to get an individual search time.