Question: 11. What is the time complexity of the following dynamic programming implementation of the rod cutting problem?<div class="hk1_style-wrap4"><div class="hk1_style-wrap3"><div class="hk1_style-wrap2"><div class="hk1_style-wrap"><div class="hk1_style"><div class="c"><pre class="de1"><span class="co2">#include&lt;stdio.h&gt;</span> <span class="co2">#include&lt;limits.h&gt;</span> <span class="kw4">int</span> rod_cut<span class="br0">(</span><span class="kw4">int</span> <span class="sy0">*</span>prices<span class="sy0">,</span> <span class="kw4">int</span> len<span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> max_val<span class="br0">[</span>len <span class="sy0">+</span> <span class="nu0">1</span><span class="br0">]</span><span class="sy0">;</span> <span class="kw4">int</span> i<span class="sy0">,</span>j<span class="sy0">,</span>tmp_price<span class="sy0">,</span>tmp_idx<span class="sy0">;</span> max_val<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span> <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span> <span class="kw1">for</span><span class="br0">(</span>i <span class="sy0">=</span> <span class="nu0">1</span><span class="sy0">;</span> i <span class="sy0">&lt;=</span> len<span class="sy0">;</span> i<span class="sy0">++</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> tmp_max <span class="sy0">=</span> INT_MIN<span class="sy0">;</span> <span class="co1">// minimum value an integer can hold</span> <span class="kw1">for</span><span class="br0">(</span>j <span class="sy0">=</span> <span class="nu0">1</span><span class="sy0">;</span> j <span class="sy0">&lt;=</span> i<span class="sy0">;</span> j<span class="sy0">++</span><span class="br0">)</span> <span class="br0">{</span> tmp_idx <span class="sy0">=</span> i <span class="sy0">-</span> j<span class="sy0">;</span> <span class="co1">//subtract 1 because index of prices starts from 0</span> tmp_price <span class="sy0">=</span> prices<span class="br0">[</span>j<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span> <span class="sy0">+</span> max_val<span class="br0">[</span>tmp_idx<span class="br0">]</span><span class="sy0">;</span> <span class="kw1">if</span><span class="br0">(</span>tmp_price <span class="sy0">&gt;</span> tmp_max<span class="br0">)</span> tmp_max <span class="sy0">=</span> tmp_price<span class="sy0">;</span> <span class="br0">}</span> max_val<span class="br0">[</span>i<span class="br0">]</span> <span class="sy0">=</span> tmp_max<span class="sy0">;</span> <span class="br0">}</span> <span class="kw1">return</span> max_val<span class="br0">[</span>len<span class="br0">]</span><span class="sy0">;</span> <span class="br0">}</span> <span class="kw4">int</span> main<span class="br0">(</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> prices<span class="br0">[</span><span class="br0">]</span><span class="sy0">=</span><span class="br0">{</span><span class="nu0">2</span><span class="sy0">,</span> <span class="nu0">5</span><span class="sy0">,</span> <span class="nu0">6</span><span class="sy0">,</span> <span class="nu0">9</span><span class="sy0">,</span> <span class="nu0">9</span><span class="sy0">,</span> <span class="nu0">17</span><span class="sy0">,</span> <span class="nu0">17</span><span class="sy0">,</span> <span class="nu0">18</span><span class="sy0">,</span> <span class="nu0">20</span><span class="sy0">,</span> <span class="nu0">22</span><span class="br0">}</span><span class="sy0">,</span>len_of_rod <span class="sy0">=</span> <span class="nu0">5</span><span class="sy0">;</span> <span class="kw4">int</span> ans <span class="sy0">=</span> rod_cut<span class="br0">(</span>prices<span class="sy0">,</span> len_of_rod<span class="br0">)</span><span class="sy0">;</span> <span class="kw3">printf</span><span class="br0">(</span><span class="st0">"%d"</span><span class="sy0">,</span>ans<span class="br0">)</span><span class="sy0">;</span> <span class="kw1">return</span> <span class="nu0">0</span><span class="sy0">;</span> <span class="br0">}</span></pre></div></div></div></div></div></div>
Options:
O(1)
O(n)
O(n2)
O(2n)
Answer: A