0

enter image description here

enter image description here

enter image description here

For the algorithm above, I can only figure out the runtime for

if n==0:

is 1 and the runtime for

rec_opt(n-1)

will be T(n-1). But I can't figure out the runtime for

rec_opt(p[n])

and why the recurrence has an exponential closed-form, O(2^n )

enter image description here

And furthermore, why this algorithm will be O(n).

yashirq
  • 123
  • 5

1 Answers1

1

rec_opt(p[n])

For recursion call rec_opt(p[n]), there will be another recursion tree which will act like rec_opt(n-1). As p[n] could be any value from 1 - n then we can assume that it will act like a rec_opt(n).

And furthermore, why this algorithm will be O(n).

On the second part as algorithm doing memoization, it will not calculate same sub-problem again and again. That's why the complexity drastically reduced to O(n).

For more please chech dynamic programming.

Community
  • 1
  • 1
MD Ruhul Amin
  • 4,386
  • 1
  • 22
  • 37
  • Now I understand rec_opt[n]. But for the runtime of the first algorithm, which is T(n) = 2T(n-1)+c, shouldn't it be O(n)? Because n is the highest term in T(n). – yashirq Oct 17 '16 at 05:04
  • If you correctly understand rec_opt(p[n]), then complexity will be clear if you try it with pen&paper. Draw a tree and count number of nodes. For the first algorithm you will see that you are doing same task again and again. – MD Ruhul Amin Oct 17 '16 at 06:16