educative.io

Exaplain time complexity in the case of memoization

Courses
,
#1

The time complexity of this code is in O(log(mn)).

Can someone explain why logarithmic time complexity?

Course: https://www.educative.io/collection/10370001/5347133077061632
Lesson: https://www.educative.io/collection/page/10370001/5347133077061632/5240259845554176

Course: https://www.educative.io/collection/10370001/5347133077061632
Lesson: https://www.educative.io/collection/page/10370001/5347133077061632/5240259845554176

#2

The statement claiming the time complexity of the given code to be O(log(mn)) is incorrect. The correct time complexity for the provided code is exponential, not logarithmic.

Let’s analyze the code:

  • The function findSIRecursive is a recursive function that explores all possible interleavings of strings m and n to form string p.
  • At each step of the recursion, it makes two recursive calls, one considering the next character from string m and the other considering the next character from string n.
  • The recursion continues until all characters from string p are matched with either string m or string n.

Since at each step, the function explores two possibilities (matching the next character from m or n), the time complexity of the recursive function is exponential, not logarithmic. It’s more accurately represented as O(2^(m+n)), where m and n are the lengths of strings m and n, respectively.

Therefore, the correct statement regarding the time complexity of the code is O(2^(m+n)), not O(log(mn)).