Robbie Jackson
Assignment 2
1. 1. As sample size increases, the run time for a sequential search increases, having a positive, linear relationship between the two. As sample size increases, the run time for a binary search remains 'constant'. Differences in run time for binary search completion would require an extremely large change in sample size. See graph above.
2. Sequential search is O(n) and binary search is O(log n). O(n) means that in worst-case scenario there will be n operations used, meaning the number you are searching for in the array in in the last or Nth-1 index. O(log n) means that every time you do an operation, you cut your sample in half, resulting in a worst-case scenario when you don't find your number after log n operations. Yes these graphs agree completely with the asymptotic run time. O(n) [sequential search] will see a great difference a sample size of 100,000 and 10,000 (O(100,000) and O(10,000) – 9x larger, 90,0000 more). O(log n) [binary search] will see a difference of O(log 100,000) and O(log 10,000) or 5 : 4 ratio in run time, which in this sample size the results will be close to negligible.