O(n) + O(n - k) can be simplified as the larger of the two terms, since adding them does not change their order of growth so shouldn’t O(n) + O(n - k) = O(n)?
Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Repeated DNA Sequences - Grokking Coding Interview Patterns in Java
Hi Daniel, though this isn’t explicitly stated in the problem (and we’ll look into that as well), the logical/sensible range of values for k is given by: 1 <= k <= n.
Thus, the worst-case scenario, changing only k, is O(n-1), that is, O(1), and the best case is O(n-n).
We do tend to make such simplifications. This is an oversight that’ll be fixed soon.
… and, of course, thanks for pointing this out!
Hi Daniel, thank you for your input and viewpoint regarding the time complexity of this problem. While it is true that simplifying the complexity to O(N) provides a high-level understanding, including the value of k in the time complexity, as O(N - k), offers a more detailed perspective. This inclusion helps us consider the impact of the substring length, k, on the algorithm’s performance.
By explicitly mentioning k, we highlight that the time complexity is dependent on the size of the sliding window, which is directly related to the length of the substrings we are examining. This additional information can be beneficial for understanding the algorithm’s behavior and potential performance optimizations.