Pattern Matching & Back-of-the-Envelope Estimations

The pattern matching problem can be stated as: Score

Given a (usually long) text string t and a (usually shorter) pattern p find where or if the pattern p occurs in t. Assume the length of t is n and the length of p is m Several algorithms were presented in the course notes to solve the pattern matching problem Here are two: • Brute-Force: The notes state the time complexity of this approach to solving the problem is O(mn). • Knuth-Morris-Pratt: The notes state the time complexity of this approach to solving the problem is O(m + n). The human genome is approximately three billion base pairs in size. the average length of a gene is approximately 30 thousand base pairs. Let m = 30, 000 and n = 3, 000, 000, 000 There are about 30, 000, 000 seconds in a year. Assume a character-to-character comparison takes 1 microsecond. Estimate the time it will take to run a brute-force algorithm. Do the same for the KMP algorithm.