The DFA is O(n) with up to exponential time spent upfront (and exponential space usage too). The exact complexity for the NFA with the regex you suggest depends on how the NFA is built, but it is at least O(n^2) worst case because you can easily build a case with n active states. Likewise for the lazy DFA.