Computer Science Homework Help

Q2: Let T be the database (the big data) of length n, and P the pattern of length m. In class we described an
algorithm for naïve pattern matching, indicating its performance in the worst case to be in O(nm) time. The naïve
algorithm does not require any preprocessing. We also provided a pseudo code for the exact steps of the naïve
pattern matching algorithm.
Provide an analysis of the naïve pattern matching algorithm to show its

Q2A: (i) best case, (ii) average case, and (iii) worst case time requirement, in terms of the Big O notation.

Q2B: (iv) best case, (v) average case, and (vi) worst case memory (space) requirement, in terms of the Big O
notation.