# Difference between revisions of "TADM2E 4.10"

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

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