Analysis of the time complexity of LINEAR SEARCH

AIM - To analyze the time complexity and behavior of linear search
algorithm and plot the acquired data.

Introduction - The following data has been obtained by running the linear search
algorithm to search an element in a randomly generated array of ‘n’ elements. The size of the array was increased continuously from 100 to 5000 with the number
inputed also being in the same range. The program was made using the ‘Python’ programming language using the ‘random’,
‘time’
and ‘matplotlib’ libraries on a computer with an Intel Core i5-6200U quad-core processor,
having 7.5GB of RAM running on Ubuntu 17.10(GNOME). The code was run using
Ubuntu’s Terminal.
The above detail is necessary as it is assumed the program was run with a machine having
different specifications.
Input - No input was given. (i) The arrays are instantiated by pre-defined loops and the values are fed into the arrays
using ‘Random’ library of Python. (ii) The element for searching in the array is also generated randomly using python
libraries. (iii) The number of times the algorithm runs is also pre-defined, equated to a thousand.


Assumptions Since any algorithm requires some prerequisites which are not often met, we assume the
following to be true: (i) The numbers generated by the random command are truly random and do not
follow any pattern. (ii) The CPU has only 1 core with single(no multithreading) threading. (iii) There is no other process being run on the CPU while this program executes till
termination.
Methodology - The program is executed using the following methodology:

1. Firstly, necessary libraries like the ‘random’ library for random number generation,
   the ‘time’ library for finding the time taken by the algorithm and the ‘matplotlib’
   library for plotting bar and line graphs are imported.
2. Next, arrays of size ranging from 100 to 5000 are programmed to be initialised
   when searching on the array of size ‘n-1’ has been performed.
3. These arrays are filled with numbers ranging from 1 to their maximum size.
4. Then, a number between the same range is randomly generated to be searched for in
   the array.
5. Algorithm for linear search is applied and the process is repeated for 100 times.
6. Lastly, time for 100 repetitions is stored in an array of 50 elements.
7. The derived result is then plotted against average time taken by the algorithm to
   execute in seconds. Also the record for the total number of successful cases is plotted
   against the size of the array.

Experiment (with observation, analysis and supporting data)-
CASE -1 : THE AVERAGE CASE For this step the search number is randomly generated and is within the range of the array elements. For Ex. for an array of size 2300, the array is filled with numbers ranging from 1 to 2300 and the search element is also present in between this range.
[ X-axis : size of the array ; Y-axis : time taken in milliseconds ] Fig: 1.1 : Line graph of linear search of arrays from 100 to 5000



Graph Analysis: As is clearly visible, the graph is a straight line with slope less than 45 degrees. The abrupt breaks or local maximas and minimas in the graph can be explained by
stating the fact that:

1. There were assumptions.
2. The randomly generated number to be searched could be anything and could be
   present anywhere in the array.

The following graph shows the number of successful searches returned in the given runs
of the array. Clearly, the number of successful searches does not vary much over the entire run of the
program. This observation clarifies the stability of the time complexity of linear search, which does
not vary with increasing array size.
[ X-axis : size of the array ; Y-axis : percentage of successful and unsuccessful
searches ]
Fig: 1.2 : Bar graph showing percentage of successful and unsuccessful searched
vs array size


CASE -2 : THE BEST CASE In the best case scenario, the element to be searched is present in the beginning of the
array and hence the search time is very short and success ratio is 100%.

[ X-axis : size of the array ; Y-axis : time taken in (10^-2)milliseconds ]
Fig: 1.3 : Line graph for best case of linear search
As is clear by the graph, the search time is very short and time complexity for best case is
‘1 or constant’.
[X-axis : size of array ; Y-axis : time taken]
Fig: 1.4 : Line graph of best case of linear search nearly parallel to the x-axis




CASE -3 : THE WORST CASE For this step the search number is ‘out-of-range’ of the array elements. This will
ensure that every run is completed from first to the last element. For Ex. for an array of size 900, containing elements from 1 to 900, a search element
equal to 1000 was passed so that nothing could be returned. This case shows the maximum time an algorithm will take for a given amount of
elements and produces the best graph.

[ X-axis : size of the array ; Y-axis : time taken in milliseconds ]
Fig:1.5 : Line graph showing worst case of linear search
Clearly, the graph is a linear line which provides us with a clear result that the
time complexity of a linear search algorithm is ‘n’.



Conclusion - It can thus be concluded that the time complexity of a linear search algorithm: In its best case : constant or O(1) In its average case : nearly O(n) In its worst case : linear or O(n) Also, it can be inferred that it is the worst case of any algorithm that decides the
final time complexity, as it describes the maximum time that can be taken by that
algorithm.
References -

1. Ask Ubuntu : http://askubuntu.com/questions/666530/ddg#666549
2. DuckDuckGO : https://duckduckgo.com/?t=canonical

--------------*--------------

WARNING : for reference purpose only, any form of copying is a violation of digital rights and policies