https://algorist.com//algowiki/index.php?title=4.9&feed=atom&action=history4.9 - Revision history2024-03-29T13:33:20ZRevision history for this page on the wikiMediaWiki 1.34.2https://algorist.com//algowiki/index.php?title=4.9&diff=309&oldid=prevAlgowikiadmin at 18:23, 20 September 20202020-09-20T18:23:24Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 18:23, 20 September 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17" >Line 17:</td>
<td colspan="2" class="diff-lineno">Line 17:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><h3>Another recursive solution</h3></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><h3>Another recursive solution</h3></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>First, we note that <del class="diffchange diffchange-inline">[[ TADM2E 4.8 | </del>an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists <del class="diffchange diffchange-inline">]]</del>, which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>First, we note that an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists, which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><pre></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><pre></div></td></tr>
</table>Algowikiadminhttps://algorist.com//algowiki/index.php?title=4.9&diff=308&oldid=prevAlgowikiadmin: Created page with "Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br /> For various values of k, <br /> k Solution Time Complexity <br /> 1 O..."2020-09-20T18:23:01Z<p>Created page with "Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br /> For various values of k, <br /> k Solution Time Complexity <br /> 1 O..."</p>
<p><b>New page</b></p><div>Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br /><br />
For various values of k, <br /><br />
k Solution Time Complexity <br /><br />
1 O(<math>n^0logn</math>) <br /><br />
2 O(<math>n^1logn</math>) <br /><br />
3 O(<math>n^2logn</math>) <br /><br />
4 O(<math>n^3logn</math>) <br /><br />
<br />
for k = 2 onwards <br /><br />
1. sort the array ( nlogn ) <br /><br />
2. use k-1 loops for iterating over array, where ith loop starts from i-1 + 1 element of array, and then use binary search <br /><br />
eg: <br /><br />
for k = 3 <br /><br />
for( i = 0; i < n; i++ ) <br /><br />
for( j = i+1; j < n; j++ ) <br /><br />
# now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br /><br />
<br />
<h3>Another recursive solution</h3><br />
First, we note that [[ TADM2E 4.8 | an O(<math>n \lg n</math>) solution for <math>k = 2</math> exists ]], which is already within the required bounds. Now, for <math>k \ge 3</math>, we can do something like this:<br />
<br />
<pre><br />
sort S ascending;<br />
CheckSumOfK(S, k, T); // defined below<br />
<br />
// S must be aorted array of integers<br />
function CheckSumOfK(S, k, T)<br />
if k <= 2:<br />
Use any method in the solution of ex 4.8 and return the result. This can be done in O(n) time because S is sorted.<br />
<br />
Initialize array A of n - 1 elements;<br />
for i from 0 to n - 1:<br />
k = 0<br />
// Collect in A all numbers in S but S[i]. Note that A will still be sorted.<br />
for j from 0 to n - 1:<br />
if i != j:<br />
A[k] = S[j];<br />
k = k + 1<br />
// If S[i] is included in the k integers that sum up to T, then there must<br />
// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).<br />
// We can find that out by calling ourselves recursively.<br />
if CheckSumOfK(A, k - 1, T - S[i]):<br />
return True<br />
return False<br />
</pre><br />
<br />
<h3>Complexity</h3><br />
For each item in S, there is <math>O(n)</math> work done in assembling the array A, except at the <math>{k - 1}^{th}</math> recursive call, which completes in <math>O(n \lg n)</math> time. So, for each number in S, we have <math>O(kn) + O(n \lg n)</math> work, and since <math>k <= n</math>, each iteration of the outer loop takes <math>O(n^2) + O(n \lg n) = O(n^2)</math><br />
work. Now since the outer loop goes on for at most <math>n</math> iterations, we have a total runtime of <math>O(n^3)</math>.<br />
<br />
A trick can be used to lower this runtime to <math>O(n^2 \lg n)</math> by having the routines in [[ TADM2E 4.8 | this solution ]] take an index to ignore when iterating in their inner loops. With this, we save the <math>O(n)</math> construction of A for every<br />
item, and then each iteration of the outer loop becomes <math>O(n \lg n)</math> (How? <math>O(k) = O(n)</math> constant time recursive calls plus <math>O(n \lg n)</math> time spent in the <math>{k - 1}^{th}</math> calls), giving a total runtime of <math>O(n^2 \lg n)</math> for <math>n</math> elements in S.<br />
<br />
Note that this cost includes the initial <math>O(n \lg n)</math> cost for sorting S. Also, this algorithm is always going to be <math>O(n^{k-1} \lg n)</math> for all <math>k >= 2</math>. The exercise just states an upper bound.<br />
<br />
<br />
Back to [[Chapter 4]]</div>Algowikiadmin