The naive solution for the repeating substring problem: -------------------------------------------------- def repeat_naive(st, k): for i in range(len(st)-k+1): for j in range(i+1,len(st)-k+1): if st[i:i+k]==st[j:j+k]: return True return False --------------------------------------------------- Complexity analysis: # of iterations: O((n-k)**2) Each iteration takes O(k): slicing, and comparison of two substrings of length k Overall complexity: O(k(n-k)**2) A solution using Hashtable class from the lecture: -------------------------------------------------- def repeat_hash1(st, k): m=len(st)-k+1 htable = Hashtable(m) for i in range(len(st)-k+1): if htable.find(st[i:i+k])==False: htable.insert(st[i:i+k]) else: return True return False -------------------------------------------------- Average case Complexity analysis: Table creation: O(n-k) # of iterations: O(n-k) Each iteration takes O(k) on average (search/insert in hashtable where the elements size is bounded by O(k) takes O(k) on average) Overall average complexity: O(n-k) + O(n-k)*O(k) = O(k(n-k)) Worst case complexity analysis: Table creation: O(n-k) # of iterations: O(n-k) Each iteration takes O((n-k)k) in the worst case (search/insert in hashtable where the elements size is bounded by O(k) takes O((n-k)k) in the worst case) Overall average complexity: O(n-k) + O(n-k)*O((n-k)k) = O(k(n-k)**2)