TADM2E 4.10

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

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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