educative.io

Educative

Top-Down solution Time Complexity

Why the final time complexity isn’t O(n * 2 ^ n), but O(2^n)? As for each element (0…n - 1) we are running LDS, which has O(2 ^ n) time complexity


Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/gx842pQXGM9

Hello @Ivan_Butrim
Thank you for pointing out the mistake. We really appreciate this.
Cheers!