oops.. 500,200 and 50,20 are values in the table.
so the algo doesnt work for this case
what if we use backtracking to find the hamiltonian cycles and
finding the min of that. It reduces the space required.since we need to
store only one cycle at one shot. am i missing the stack space required
of recursion of backtrack.??
Dhyanesh, what about time. does it reduces the time as well??
one correction --- while ( k 0) this should be while ( k
0)
my idea is like this:
1/ find a number k in the array where k-z is minimum.
2/ then arrange the array in such a way that array[1...r] contains the
numbers less than z, a[r] contains the k , a[r+1, .. n] contains the
numbers greater than z.
( like one iteration of quick sort, if i remember
yes. you are calucation is wrong in You are againing need to do
n/2 * n/2 comparing... .
moving heads in step 3 will take only O(n).
T(n) = O(n).
please see the step 3 again/.
