option B) is correct answer, Without DP – O(2^n) , using masters theorem
Using DP – every time time result is calculated store it in an array, if result is already computed then there is no need to compute it again. Therefore in worst case complexity is O(n) ie size of the array.