Algorithm without dynamic programming,less efficient solution

Question

There is a problem asked in contest. I already solved this problem with dynamic programming and its complexity O(n^2). But i am looking for solution with less efficient way. What will be the complexity of this less efficient way. Thanks for the helps.

I guess you mean "more efficient way"? Otherwise, its easy to make the algorithm arbitrarily inefficient. — Henry
– Henry, Commented Dec 27, 2012 at 9:59
i mean less efficent way. I would like to compare their complexity.For instance i am looking for a O(n^3) solution — sekogs
– sekogs, Commented Dec 27, 2012 at 10:03
@mustad: O(n^2) is a subset of O(n^3), so an O(n^2) solution is also an O(n^3) solution. — amit
– amit, Commented Dec 27, 2012 at 10:45
@amit assume Theta(n^3); it's still trivial to make an algorithm arbitrarily slow. — John Dvorak
– John Dvorak, Commented Dec 27, 2012 at 10:45
By the way, did you know you can sort arrays in Th((3/2)^n)? — John Dvorak
– John Dvorak, Commented Dec 27, 2012 at 10:48

Patricia Shanahan · Accepted Answer · 2012-12-27 17:29:25Z

2

There is a general way to make any dynamic programming solution less efficient. The essence of dynamic programming is to store solutions to sub-problems for reuse.

To make it less efficient in a somewhat reasonable way, get rid of the sub-problem result storage. Instead, recalculate each sub-problem solution whenever you need it.

answered Dec 27, 2012 at 17:29

Patricia Shanahan

26.2k4 gold badges42 silver badges75 bronze badges

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

Comments

Ante · Accepted Answer · 2012-12-27 16:24:25Z

1

Using inefficient data structure with same algorithm can help to have O(n^3). Storing towns in a linked list instead of an array will make algorithm one order less efficient.

To make it even less efficient, it is easier to change algorithm. For example checking of all harbinger changing combinations and using minimal, which is exponential in time.

edited Dec 27, 2012 at 16:24

answered Dec 27, 2012 at 16:16

Ante

5,4686 gold badges26 silver badges47 bronze badges

Collectives™ on Stack Overflow

Algorithm without dynamic programming,less efficient solution

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related