Brute-force LCS algorithm Check every subsequence of[1. m to see if it is also a subsequence of[l Analysis Checking =O(n) time per subsequence 2m subsequences of x(each bit-vector of length m determines a distinct subsequence OIX Worst-case running time=O(n2m exponential time c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.3© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.3 Brute-force LCS algorithm Check every subsequence of x[1 . . m] to see if it is also a subsequence of y[1 . . n]. Analysis • Checking = O(n) time per subsequence. • 2m subsequences of x (each bit-vector of length m determines a distinct subsequence of x). Worst-case running time = O(n2m) = exponential time