educative.io

Repeated DNA Sequences worst case time complexity

Just wanted to know why we use polynomial rolling hash in when worst case time complexity is practically the same as Naive approach


Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Repeated DNA Sequences

1 Like

Hello @KO-65,

Thank you for sharing this feedback.

Even though the worst case time complexity remains the same, the average case time complexity is significantly improved, since we’re only generating a k-length substring when a repeated sequence is encountered.

Please feel free to share any more feedbacks or suggestions. We’d be happy to help. Thanks!

Happy learning!

1 Like