# 4.9

Here the main thing to notice is that we need a O(${\displaystyle n^{k-1}logn}$) solution.
For various values of k,
k Solution Time Complexity
1 O(${\displaystyle n^{0}logn}$)
2 O(${\displaystyle n^{1}logn}$)
3 O(${\displaystyle n^{2}logn}$)
4 O(${\displaystyle n^{3}logn}$)

for k = 2 onwards
1. sort the array ( nlogn )
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
eg:
for k = 3
for( i = 0; i < n; i++ )
for( j = i+1; j < n; j++ )

1. now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array

### Another recursive solution

First, we note that an O(${\displaystyle n\lg n}$) solution for ${\displaystyle k=2}$ exists, which is already within the required bounds. Now, for ${\displaystyle k\geq 3}$, we can do something like this:

```sort S ascending;
CheckSumOfK(S, k, T); // defined below

// S must be aorted array of integers
function CheckSumOfK(S, k, T)
if k <= 2:
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.

Initialize array A of n - 1 elements;
for i from 0 to n - 1:
k = 0
// Collect in A all numbers in S but S[i]. Note that A will still be sorted.
for j from 0 to n - 1:
if i != j:
A[k] = S[j];
k = k + 1
// If S[i] is included in the k integers that sum up to T, then there must
// exactly (k - 1) integers in the rest of S (i.e., A) that sum to (T - S[i]).
// We can find that out by calling ourselves recursively.
if CheckSumOfK(A, k - 1, T - S[i]):
return True
return False
```

### Complexity

For each item in S, there is ${\displaystyle O(n)}$ work done in assembling the array A, except at the ${\displaystyle {k-1}^{th}}$ recursive call, which completes in ${\displaystyle O(n\lg n)}$ time. So, for each number in S, we have ${\displaystyle O(kn)+O(n\lg n)}$ work, and since ${\displaystyle k<=n}$, each iteration of the outer loop takes ${\displaystyle O(n^{2})+O(n\lg n)=O(n^{2})}$ work. Now since the outer loop goes on for at most ${\displaystyle n}$ iterations, we have a total runtime of ${\displaystyle O(n^{3})}$.

A trick can be used to lower this runtime to ${\displaystyle O(n^{2}\lg n)}$ by having the routines in this solution take an index to ignore when iterating in their inner loops. With this, we save the ${\displaystyle O(n)}$ construction of A for every item, and then each iteration of the outer loop becomes ${\displaystyle O(n\lg n)}$ (How? ${\displaystyle O(k)=O(n)}$ constant time recursive calls plus ${\displaystyle O(n\lg n)}$ time spent in the ${\displaystyle {k-1}^{th}}$ calls), giving a total runtime of ${\displaystyle O(n^{2}\lg n)}$ for ${\displaystyle n}$ elements in S.

Note that this cost includes the initial ${\displaystyle O(n\lg n)}$ cost for sorting S. Also, this algorithm is always going to be ${\displaystyle O(n^{k-1}\lg n)}$ for all ${\displaystyle k>=2}$. The exercise just states an upper bound.

Back to Chapter 4