Just need someone to rewrite and proof read my one page code write up about about my timing study
Timing Study: Linear Search vs. Binary Search
Purpose
The purpose of this assignment was to compare the performance of Linear Search and Binary Search as the size of the array (N) increases. Since Binary Search requires a sorted array, Insertion Sort was used before performing Binary Search. The time for sorting was included in the Binary Search timing.
Method
For this experiment, arrays of random numbers were generated for different sizes of N. The sizes tested were increasing values such as 100, 500, 1000, 2000, 5000, and 10000.
For each array, the following steps were performed:
- An array of N random integers was created.
- A random index between 0 and N-1 was selected.
- The value at that index was used as the search target.
- Linear Search was performed and timed.
- A copy of the array was sorted using Insertion Sort.
- Binary Search was performed on the sorted array.
- The total time for sorting and Binary Search was recorded.
The time.perf_counter() function in Python was used to measure execution time.
Results
As the value of N increased, the time for Linear Search increased steadily. The time for Binary Search alone is very small, but when combined with Insertion Sort, the total time increased much faster.
For small values of N, both methods performed quickly. However, for larger values of N, Binary Search with Insertion Sort took significantly longer than Linear Search.
Analysis
The results match the expected time complexities of the algorithms. Linear Search has a time complexity of O(n). Insertion Sort has a time complexity of O(n2). Binary Search has a time complexity of O(log n).
Even though Binary Search is faster than Linear Search by itself, the required sorting step makes the overall process much slower. Since Insertion Sort is O(n2), it dominates the total runtime.
This explains why Binary Search with sorting became slower than Linear Search for large arrays.
Conclusion
This experiment shows that the overall efficiency of an algorithm depends on all steps involved. Although Binary Search is very efficient, the need to sort the array using Insertion Sort makes it less practical for large datasets. Linear Search performed better overall when sorting time was included.
If a faster sorting algorithm such as Merge Sort (O(n log n)) were used, Binary Search would likely outperform Linear Search for large values of N.
Attached Files (PDF/DOCX): Timing Study.docx
Note: Content extraction from these files is restricted, please review them manually.