Back to course home
0% completed
Vote For New Content
Time Complexity
cogom
Jul 4, 2023
Could you explain why the time complexity will be O(4^n), not O(m * n * 4^n)? The recursive dfs functions will indeed take O(4^n), but I thought we call it m * n times in the extreme case.. Thank you in advance!
2
0
Comments
Comments
U
Utkarsh Gupta2 years ago
You are right. The exact time complexity would be O(m * n * 3 ^n) because initially, we could have at most 4 directions to explore, but further the choices are reduced into 3 (since we won't go back to where we come from)
On this page