finding the count of a number of terms in a list
Is there an algorithm lees than O(n^2) for this?
I'm not sure I understand the question, I think you need to be more precise.
David Basil Wildgoose
Sumit, are you making the list yourself, or is it given to you by some(one|thing) else?
If you mean you want to find the number of times each element of the list appears in the list, then - yes, you can do it in O(n) average with a hash, or O(n log n) worst case with a balanced tree of some sort.
I am making the list myself, I am trying to find the number of duplicates in a sentence, how can I do this in less than O(n^2), by using say a hash?
Yes you should use a hash to count the number of terms. They are orders of magnitude faster than scanning arrays.
To clarify create in the loop that scans your sentence create a hash for each word you find and increment it by one. At the end of the loop your hash will contain a count of the words in the sentence.
You can sort a list in O(n log n) steps, and then find duplicates in the sorted list in O(n) steps.
you view the sentence as a 'list of words'; are there other ways to view it?
How can I find duplicates in the list in O(n) steps?
Without using a hash I think the best approach is to first sort the list using the fastest means possible.
I don't see how using a hash could require a lot of changes in your code. As I understand, you use the hash only to find your number of duplicates, and throw it away afterwards.
Albert D. Kallal
use SQL :=)
You find the duplicates as you create the list, whether you hash/index or not depends on whether you care about this at some later date, ie you store the occurrence of duplication.
This sounds like a job for...
You can get O(1) if you want.
Fog Creek Home