TADM2E 4.10

From Algorithm Wiki
Revision as of 17:49, 6 February 2015 by Upcomingnewton (Talk | contribs)

Jump to: navigation, search

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