educative.io

Why is the time complexity for minimum window subsequence is O(m*n)?

Courses
,
#1

Hi, I am trying to understand the time complexity of the minimum window subsequence problem. We have an outer loop and then a loop inside it that travels backwards, so it seems like worst case would be O(m*m)?

Course: https://www.educative.io/courses/grokking-coding-interview-patterns-javascript
Lesson: Solution: Minimum Window Subsequence - Grokking Coding Interview Patterns in JavaScript

#2

Hi @Siri_S !!
Thanks for contacting us. In this problem, we used two loops, an outer loop for str1 and an inner loop for str2. The time complexity of this solution is O(m* n) where m is the length of the str2 and n
n is the length of str1.
I hope it helps. Happy Learning :slight_smile: