Question

Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?

(a) O(n^2)

(b) O(n^3)

(c) O(nlogn)

(d) O(2^n)

This question was addressed to me during an internship interview.

This is a very interesting question from Rod Cutting topic in division Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right choice is (d) O(2^n)

The explanation is: The brute force implementation finds all the possible cuts. This takes O(2^n) time.