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