educative.io

Clarification on the runtime of naive approach for DNA Sequences

Courses
,
#1

For the naive approach of this problem, it says the runtime is O((n-k)*k).
I understand the (n-k) part but for each one, it says we do k amount of work to create the string from the array. However, don’t we also need to check if the string is in the set? If the size of the set is “s” won’t it be O(s + k)? Or are we assuming that the set is a hashtable, hence the lookup is constant?

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

#2

Hello @Enki1,

The algorithm’s time complexity is O((n - k) * k) due to its iterations and set lookups. Set lookups are typically constant time. In the worst case, if all k-length substrings are unique, each iteration involves O(1) set lookup time.

Thanks and regards,
Dian Us Suqlain
Developer Advocate @Educative.io

#3

Hi Dian, another question :slight_smile:
In the final solution of this problem, I see that we do output.add(s.substring(i, i + k));
In line 36.
If it’s the worst case and the input is all the same characters, the runtime would be O((n - k -1) * k) right?Thinking that the substring operation would be O(k) runtime, and if we do that for each of the subsequent k windows, it would be n-k-1 times. So in the worst case, the runtime would be the same as the naive approach right?

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

#4

Hello @Enki1,

The algorithm’s time complexity remains O(n) . This is because hashSet and output are both hash sets. Therefore, the .has and .add methods will take O(1) time regardless of what input string is given.

Hope this answers your query. Feel free to share any more suggestions and feedbacks.

Happy learning!