Compare 3 simple search algorithms and their running time growths in Big-O notations
Suppose you have a sorted array of integers and would like to determine if there exists an element x, such that x and -x are both in the array. For example:
- For the array <-4, -2, 1, 3, 5, 7, 9>, the algorithm returns false, because there is no element whose negative is in the array
- For the array <-4, -2, 1, 2, 3, 5, 7, 9> then the algorithm returns true, since 2 and -2 are both in the array
I coded 3 different searching algorithms to see if x's negative is in the array and tested the algorithms' worst-case running times in Big-O notations relative to n, the lenght of the array:
- A naive sequential search| O(n^2).
- A binary search | O(nlog_2(n))
- A index-based search | O(n)
More details in code
Timing of algorithm was done for different input sizes:
- 25,000
- 50,000
- 100,000
- 200,000
- 400,000