Arrays in C++ – Finding appropriate pairs in an array – 4
March 8, 2011 Leave a comment
APPROACH 3 contd.
Now, what if we remove the 2 assumptions we made earlier –
1. all elements in A are distinct.What if duplicates are now allowed?
2. Array A contains elements only in the range 0 – 99. What if the ints in A can have any possible value?
If we remove the first restriction, we would possibly need to print a pair more than once depending on the number of times each element of the pair appears in A.
For example, if 10 appears thrice and 25 appears twice, and our target is 35, then we would need to print the 10, 25 pairs 6 times.
Let’s now look at removing the 2nd restriction.
Earlier we were able to declare a lookup array L of a constant size =100 because of the simplifying assumption on the range of possible values in A.
Now, if all values are allowed, the size of the lookup table would have to be (assuming sizeof(int) == 4).
Making these 2 modifications, we would be able to tackle the problem.
There are a couple of observations on running time complexity that we would like to make here —
1. Whenever we want to decide which algorithm to go for, it is a good idea to look at both the time and space complexities of the algorithms concerned. Also, for a very large input size, the asymptotic i.e. big-O analysis provides a fairly accurate estimate of the complexity. However, for small input sizes, one should be careful to see what the hidden constants in the big-O notation are, as it is possible that for small input sizes these hidden constants may be the dominating factor in deciding the actual time it takes to run the algorithm.
2. If we are going to perform a similar type of query a number of times, then it makes sense to construct a sort of lookup table which can be used with minimal overhead for future queries. The time/ space required to construct the lookup table can be made to seem insignificant if the number of queries based on that table is large. However, if we are just going to make a single query of a particular type, then one would need to carefully decide if it is worth allocating a large amount of memory for a lookup table and using up a large amount of time to construct it, given that we would be using it only once.