Note if using Colab
First download linkedlist.py to your machine.
Click ">" button to right of code. Select files and upload the linkedlist.py file. This must be done each new run in Colab.
Simple Linear Search algorithm
We expect running time where is the length of the array or list.
Binary Search
We expect running time when using an array and when using a linked list.
It might be preferable to use a non-recursive binary search as the recursive one actually builds new sub-arrays in the recursion steps. The following simply resets indices.
Functions to time runs
This function takes two parameter , the number of items in the list, and the number of repititions for this . It is good to repeat so as to smooth out some of the noise in the system.
Test run time of LinearSearch
First run on arrays.
A few models to fit
Fit a model and plot the result
We expect LinearSearch to have running time. So try the linear
fit.
Repeat analysis of Linear Search with linked lists
Notice, the running time has increased but the linear model is still correct.
Repeat analysis for binary search
Here we expect running time, so try to model with log_n
fit function.
Analysis of binary search using linked lists
Here our analysis suggests .