Question: 5. What will be the time complexity of the following code?<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;bits/stdc++.h&gt; </span> using namespace std<span class="sy0">;</span> &nbsp; <span class="kw4">int</span> min<span class="br0">(</span><span class="kw4">int</span> x<span class="sy0">,</span> <span class="kw4">int</span> y<span class="br0">)</span> <span class="br0">{</span> <span class="kw1">return</span> <span class="br0">(</span>x <span class="sy0">&lt;</span> y<span class="br0">)</span><span class="sy0">?</span> x<span class="sy0">:</span> y<span class="sy0">;</span> <span class="br0">}</span> &nbsp; <span class="kw4">int</span> func<span class="br0">(</span><span class="kw4">int</span> arr<span class="br0">[</span><span class="br0">]</span><span class="sy0">,</span> <span class="kw4">int</span> n<span class="br0">)</span> <span class="br0">{</span> &nbsp; <span class="kw4">int</span> <span class="sy0">*</span>jump <span class="sy0">=</span> new <span class="kw4">int</span><span class="br0">[</span>n<span class="br0">]</span><span class="sy0">;</span> <span class="kw4">int</span> i<span class="sy0">,</span> j<span class="sy0">;</span> &nbsp; <span class="kw1">if</span> <span class="br0">(</span>n <span class="sy0">==</span> <span class="nu0">0</span> <span class="sy0">||</span> arr<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span> <span class="sy0">==</span> <span class="nu0">0</span><span class="br0">)</span> <span class="kw1">return</span> INT_MAX<span class="sy0">;</span> &nbsp; jump<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> &nbsp; <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> n<span class="sy0">;</span> i<span class="sy0">++</span><span class="br0">)</span> <span class="br0">{</span> jump<span class="br0">[</span>i<span class="br0">]</span> <span class="sy0">=</span> INT_MAX<span class="sy0">;</span> <span class="kw1">for</span> <span class="br0">(</span>j <span class="sy0">=</span> <span class="nu0">0</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> <span class="kw1">if</span> <span class="br0">(</span>i <span class="sy0">&lt;=</span> j <span class="sy0">+</span> arr<span class="br0">[</span>j<span class="br0">]</span> <span class="sy0">&amp;&amp;</span> jumps<span class="br0">[</span>j<span class="br0">]</span> <span class="sy0">!=</span> INT_MAX<span class="br0">)</span> <span class="br0">{</span> jump<span class="br0">[</span>i<span class="br0">]</span> <span class="sy0">=</span> min<span class="br0">(</span>jump<span class="br0">[</span>i<span class="br0">]</span><span class="sy0">,</span> jump<span class="br0">[</span>j<span class="br0">]</span> <span class="sy0">+</span> <span class="nu0">1</span><span class="br0">)</span><span class="sy0">;</span> <span class="kw2">break</span><span class="sy0">;</span> <span class="br0">}</span> <span class="br0">}</span> <span class="br0">}</span> <span class="kw1">return</span> jump<span class="br0">[</span>n<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="sy0">;</span> <span class="br0">}</span> &nbsp; <span class="kw4">int</span> main<span class="br0">(</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> arr<span class="br0">[</span><span class="br0">]</span> <span class="sy0">=</span> <span class="br0">{</span><span class="nu0">1</span><span class="sy0">,</span> <span class="nu0">3</span><span class="sy0">,</span> <span class="nu0">6</span><span class="sy0">,</span> <span class="nu0">1</span><span class="sy0">,</span> <span class="nu0">9</span><span class="sy0">,</span><span class="nu0">7</span><span class="br0">}</span><span class="sy0">;</span> <span class="kw4">int</span> size <span class="sy0">=</span> <span class="kw4">sizeof</span><span class="br0">(</span>arr<span class="br0">)</span><span class="sy0">/</span><span class="kw4">sizeof</span><span class="br0">(</span><span class="kw4">int</span><span class="br0">)</span><span class="sy0">;</span> cout<span class="sy0">&lt;&lt;</span> func<span class="br0">(</span>arr<span class="sy0">,</span>size<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(n log n)
O(n)
O(n1/2)
O(n2)
Answer: D