Difference between revisions of "TADM2E 4.10"
From Algorithm Wiki
(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>...") |
|||
| Line 1: | Line 1: | ||
| − | Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. | + | Here the main thing to notice is that we need a O(<math>n^{k-1}logn</math>) solution. <br /> |
| − | For various values of k, | + | For various values of k, <br /> |
| − | k Solution Time Complexity | + | k Solution Time Complexity <br /> |
| − | 1 O(<math>n^0logn</math>) | + | 1 O(<math>n^0logn</math>) <br /> |
| − | 2 O(<math>n^1logn</math>) | + | 2 O(<math>n^1logn</math>) <br /> |
| − | 3 O(<math>n^2logn</math>) | + | 3 O(<math>n^2logn</math>) <br /> |
| − | 4 O(<math>n^3logn</math>) | + | 4 O(<math>n^3logn</math>) <br /> |
| − | for k = 2 onwards | + | for k = 2 onwards <br /> |
| − | 1. sort the array ( nlogn ) | + | 1. sort the array ( nlogn ) <br /> |
| − | 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 | + | 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 <br /> |
| − | eg: | + | eg: <br /> |
| − | for k = 3 | + | for k = 3 <br /> |
| − | for( i = 0; i < n; i++ ) | + | for( i = 0; i < n; i++ ) <br /> |
| − | for( j = i+1; j < n; j++ ) | + | for( j = i+1; j < n; j++ ) <br /> |
| − | # now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array | + | # now use binary search to find ( T - a[i] - a[j] ) from j+1 element to end of array <br /> |
Revision as of 17:49, 6 February 2015
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
