🔒 Locked

Introduction to Algorithms

Started by Penguinzchaseme Jun 29, 2004 at 3:50 PM 0 replies 600+ views

Original Post

Jun 29, 2004 at 3:50 PM

I just got my first algorithm book - Introduction to algorithms by Thomas H. Cormen - and it's grrrrrreat! However, I'm stuck on two problems in the first chapter :) The first: Describe a O(n lg n) algorithm that given a set of numbers, determine whether there are two numbers in the set that sum to get another given number, x The second: Inversions are defined that in an array if i < j and A > A[j] then (i,j) is an inversion. give an O(n lg n) algorthim that determines the number of inversions in a given array. Thanks alot you all and I really recommend this book to anyone interested in algorithms

Matei

Jun 29, 2004 at 4:28 PM

In both problems, the O(N log N) bound looks very familiar - sorting has this bound! So, it might help to sort the arrays:

For the first problem, one approach is to test for each element e whether there is one whose sum with e is x. That element would have to be equal to x-e. So this is a matter of a simple search. Sort the array, then use binary searches, and you've got it: O(N log N) time to sort the array, then N searches which each take O(log N) time. In fact, you can reduce the second part to linear, since if you take the elements in increasing order you know that any element equal to x-e[i+1] should be before or equal to the least element less than or equal to x-e, so you can just scan backwards. That doesn't improve the overall complexity though, so don't worry about it ;).

For the second problem, compare each element's position in the sorted array with its position in the original array. I think the number of inversions will be the sum of the differences in positions, divided by 2... You might want to try proving it to be certain though.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.