What is the asymptotic running time of this code? def longest substring(s t): Fi

Question

What is the asymptotic running time of this code?

def longest substring(s t): Finds the longest substring that occurs in both s and t best for length. in range (min (len(s) ,len (t)) +1) ans k substring s, t, length) if ans is None return best best ans return best He f k substring(s, t, k): "Finds a substring of length k in both s and t if there is one, and returns it. Otherwise, returns None." s substrings set Put all substrings of s of length k into a set s substrings for s start in range len (s)-k current SI s start s start+k] s substrings add (current) For every substring of t of length k, look for it in s substrings If it's there return. it. for t start in range (len (t) -k current at[t start t start+k] if current in s substrings return current return None

Explanation / Answer

As per given code after analyzing the firts part of the code is having one for loop..
This loop will run the len(t) times..so the time complexcity is O(t)

As per given second def method is having two for loops individually.
each for loop will run the len(s) times..the length is O(s)..
Similarly second for loop will run O(S) times.
Total time complexcity is O(t+s).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.