TADM2E 4.10
From Algorithm Wiki
Revision as of 17:48, 6 February 2015 by Upcomingnewton (talk | contribs) (Created page with "Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. For various values of k, k Solution Time Complexity 1 O(<math>n^0logn</math>...")
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
