Runtime for recursive algorithm

Question

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 )

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

Community · Accepted Answer · 2017-05-23 12:00:43Z

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.

edited May 23, 2017 at 12:00

CommunityBot

11 silver badge

answered Oct 17, 2016 at 4:09

MD Ruhul Amin

4,5022 gold badges24 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

yashirq Over a year ago

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

MD Ruhul Amin Over a year ago

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.

Collectives™ on Stack Overflow

Runtime for recursive algorithm

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related