CODEWITHSUNDEEP
algorithmrecursionruntime
yashirq
yashirq

Reputation: 123

Runtime for recursive algorithm

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).

Upvotes: 0

Views: 422

Answers (1)

MD Ruhul Amin
MD Ruhul Amin

Reputation: 4502

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.

Upvotes: 1

Related Questions