Question: 10. What is the space complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?<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;string.h&gt;</span> <span class="kw4">int</span> get_min<span class="br0">(</span><span class="kw4">int</span> a<span class="sy0">,</span> <span class="kw4">int</span> b<span class="br0">)</span> <span class="br0">{</span> <span class="kw1">if</span><span class="br0">(</span>a <span class="sy0">&lt;</span> b<span class="br0">)</span> <span class="kw1">return</span> a<span class="sy0">;</span> <span class="kw1">return</span> b<span class="sy0">;</span> <span class="br0">}</span> <span class="kw4">int</span> edit_distance<span class="br0">(</span><span class="kw4">char</span> <span class="sy0">*</span>s1<span class="sy0">,</span> <span class="kw4">char</span> <span class="sy0">*</span>s2<span class="br0">)</span> <span class="br0">{</span> <span class="kw4">int</span> len1<span class="sy0">,</span>len2<span class="sy0">,</span>i<span class="sy0">,</span>j<span class="sy0">,</span>min<span class="sy0">;</span> len1 <span class="sy0">=</span> <span class="kw3">strlen</span><span class="br0">(</span>s1<span class="br0">)</span><span class="sy0">;</span> len2 <span class="sy0">=</span> <span class="kw3">strlen</span><span class="br0">(</span>s2<span class="br0">)</span><span class="sy0">;</span> <span class="kw4">int</span> arr<span class="br0">[</span>len1 <span class="sy0">+</span> <span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>len2 <span class="sy0">+</span> <span class="nu0">1</span><span class="br0">]</span><span class="sy0">;</span> <span class="kw1">for</span><span class="br0">(</span>i <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span>i <span class="sy0">&lt;=</span> len1<span class="sy0">;</span> i<span class="sy0">++</span><span class="br0">)</span> arr<span class="br0">[</span>i<span class="br0">]</span><span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span> <span class="sy0">=</span> i<span class="sy0">;</span> <span class="kw1">for</span><span class="br0">(</span>i <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span> i <span class="sy0">&lt;=</span> len2<span class="sy0">;</span> i<span class="sy0">++</span><span class="br0">)</span> arr<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span><span class="br0">[</span>i<span class="br0">]</span> <span class="sy0">=</span> i<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> len1<span class="sy0">;</span> i<span class="sy0">++</span><span class="br0">)</span> <span class="br0">{</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> len2<span class="sy0">;</span> j<span class="sy0">++</span><span class="br0">)</span> <span class="br0">{</span> min <span class="sy0">=</span> get_min<span class="br0">(</span>arr<span class="br0">[</span>i<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>j<span class="br0">]</span><span class="sy0">,</span>arr<span class="br0">[</span>i<span class="br0">]</span><span class="br0">[</span>j<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="br0">)</span> <span class="sy0">+</span> <span class="nu0">1</span><span class="sy0">;</span> <span class="kw1">if</span><span class="br0">(</span>s1<span class="br0">[</span>i <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span> <span class="sy0">==</span> s2<span class="br0">[</span>j <span class="sy0">-</span> <span class="nu0">1</span><span class="br0">]</span><span class="br0">)</span> <span class="br0">{</span> <span class="kw1">if</span><span class="br0">(</span>arr<span class="br0">[</span>i<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>j<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span> <span class="sy0">&lt;</span> min<span class="br0">)</span> min <span class="sy0">=</span> arr<span class="br0">[</span>i<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>j<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="sy0">;</span> <span class="br0">}</span> <span class="kw1">else</span> <span class="br0">{</span> <span class="kw1">if</span><span class="br0">(</span>arr<span class="br0">[</span>i<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>j<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span> <span class="sy0">+</span> <span class="nu0">1</span> <span class="sy0">&lt;</span> min<span class="br0">)</span> min <span class="sy0">=</span> arr<span class="br0">[</span>i<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span><span class="br0">[</span>j<span class="sy0">-</span><span class="nu0">1</span><span class="br0">]</span> <span class="sy0">+</span> <span class="nu0">1</span><span class="sy0">;</span> <span class="br0">}</span> arr<span class="br0">[</span>i<span class="br0">]</span><span class="br0">[</span>j<span class="br0">]</span> <span class="sy0">=</span> min<span class="sy0">;</span> <span class="br0">}</span> <span class="br0">}</span> <span class="kw1">return</span> arr<span class="br0">[</span>len1<span class="br0">]</span><span class="br0">[</span>len2<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">char</span> s1<span class="br0">[</span><span class="br0">]</span> <span class="sy0">=</span> <span class="st0">"abcd"</span><span class="sy0">,</span> s2<span class="br0">[</span><span class="br0">]</span> <span class="sy0">=</span> <span class="st0">"defg"</span><span class="sy0">;</span> <span class="kw4">int</span> ans <span class="sy0">=</span> edit_distance<span class="br0">(</span>s1<span class="sy0">,</span> s2<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(m + n)
O(mn)
O(n)
Answer: D