# TADM2E 4.10

From Algorithm Wiki

Revision as of 17:48, 6 February 2015 by Upcomingnewton (Talk | contribs)

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++ )

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