educative.io

Brute-Force Time and Space Complexity

Courses
,
#1

In the brute-force solution, shouldn’t the time complexity be O(2^(m + n)) instead of just O(2^m) and the space complexity O(m + n) instead of just O(m)?

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: Subsequence Pattern Matching - Grokking Dynamic Programming Patterns for Coding Interviews

#2

Hi @Vrdko93, Thanks for reaching out to us.

  • The space complexity of this algorithm is O(m) since the depth of the recursion tree will be at most m, each time we move to the next character in the string.
  • The time complexity of this algorithm is O(2^m) as our recursion stack will not be deeper than m.

Hope it will help :slight_smile: